KMP和扩展KMP

kmp算法：
模式串在主串中出现首次位置以及出现次数

//模式串在主串中出现首次位置 以及出现次数
#include <bits/stdc++.h>
using namespace std;
const int maxx = 100010;
int next[maxx];
char s1[maxx],s2[maxx];
int len1,len2;
void getnext()
{
  int j=0;
  int k=-1;
  next[0] = -1;
  while(j < len2)
      if(k == -1 || s2[j] == s2[k])
          next[++j] = ++k;
      else
          k = next[k];
}
//返回模式串s2在主串s1首次出现的位置 返回的位置从0开始的
int kmp_index()
{
  int i=0,j=0;
  getnext();
  while(i < len1 && j < len2)
  {
      if(j == -1 || s1[i] == s2[j])
          i++,j++;
      else
          j = next[j];
  }
  if(j == len2)
      return i- len2;
  return -1;
}
//返回模式串在主串出现的次数
int kmp_count()
{
  int ans = 0;
  int i,j=0;
  if(len1 == 1 && len2 == 1)
  {
      if(s1[0] == s2[0])
          return 1;
      return 0;
  }
  getnext();
  for(i=0;i<len1;i++)
  {
      while(j > 0 && s1[i] != s2[j])
          j = next[j];
      if(s1[i] == s2[j])
          j++;
      if(j == len2)
      {
          ans++;
          cout<<"j = "<<j<<endl;
          j = next[j];
      }
  }
  return ans;
}
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
      cin>>s1>>s2;
      len1 = strlen(s1);
      len2 = strlen(s2);
      cout<<"模式串s2在主串s1中首次出现的位置是 "<<kmp_index()<<endl;
      cout<<"模式串s2在主串s1中出现的次数是 "<<kmp_count()<<endl;
  }
  return 0;
}

扩展KMP算法：
定义母串S和子串T，S的长度为n，T的长度为m；
求字符串T 与字符串S的每一个后缀的最长公共前缀；

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
#define ll long long
const int MAX=1000010; //字符串长度最大值
int next1[MAX],extend[MAX];
char a[MAX],b[MAX];
//预处理计算Next数组
void getNext(char str[])
{
  int i=0,j,po,len=strlen(str);
  next1[0]=len; //初始化next[0]
  while(str[i]==str[i+1] && i+1<len) i++; next1[1]=i; //计算next[1]
  po=1; //初始化po的位置
  for(i=2;i<len;i++)
  {
      if(next1[i-po]+i < next1[po]+po) //第一种情况，可以直接得到next[i]的值
          next1[i]=next1[i-po];
      else //第二种情况，要继续匹配才能得到next[i]的值
      {
          j = next1[po]+po-i;
          if(j<0) j=0; //如果i>po+next[po],则要从头开始匹配
          while(i+j<len && str[j]==str[j+i]) j++; next1[i]=j;
          po=i; //更新po的位置
      }
  }
}
//计算extend数组
void EXKMP(char s1[],char s2[])
{
  int i=0,j,po,len=strlen(s1),l2=strlen(s2);
  getNext(s2); //计算子串的next数组
  while(s1[i]==s2[i] && i<l2 && i<len) i++; extend[0]=i;
  po=0; //初始化po的位置
  for(i=1;i<len;i++)
  {
      if(next1[i-po]+i < extend[po]+po) //第一种情况，直接可以得到extend[i]的值
          extend[i]=next1[i-po];
      else //第二种情况，要继续匹配才能得到extend[i]的值
      {
          j = extend[po]+po-i;
          if(j<0) j=0; //如果i>extend[po]+po则要从头开始匹配
          while(i+j<len && j<l2 && s1[j+i]==s2[j]) j++; extend[i]=j;
          po=i; //更新po的位置
      }
  }
}
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
      memset(extend,0,sizeof(extend));
      memset(next1,0,sizeof(next1));
      scanf("%s%s",a,b);
      int l = strlen(a);
      EXKMP(a,b);
      for(int i=0;i<l;i++){
          printf("%d ",extend[i]);
      }
  }
  return 0;

}

```