KMP模板

KMP算法的重点就是next数组的处理

具体理解课参考这篇博客：​​点击这里​​

模板：

普通版本：

void GetNext(char* p,int next[])
{
  int pLen=strlen(p);
  next[0]=-1;
  int k=-1;
  int j=0;
  while(j<pLen)
  {
    //p[k]表示前缀，p[j]表示后缀
    if(k==-1||p[j]==p[k]) 
    {
      ++k;
      ++j;
      next[j]=k;
    }
    else 
    {
      k=next[k];
    }
  }
}

abcd
-1 0 0 0 0
1
aaaa
-1 0 1 2 3
4
ababab
-1 0 0 1 2 3 4
3

next[0]=0:

void GetNext(char* p, int next[])
{
    next[0]=next[1]=0;
    int m=strlen(p);
    for(int i=1; i<m; i++)
    {
        int j=next[i];
        while(j && p[i]!=p[j])
            j=next[j];
        next[i+1]=(p[i]==p[j])?j+1:0;
    }
}

/*abcd
0 0 0 0 0
1
aaaa
0 0 1 2 3
4
ababab
0 0 0 1 2 3 4
3*/

优化版

void GetNextval(char* p, int next[])
{
  int pLen=strlen(p);
  next[0]=-1;
  int k=-1;
  int j=0;
  while(j<pLen)
  {
    //p[k]表示前缀，p[j]表示后缀  
    if(k==-1||p[j]==p[k])
    {
      ++j;
      ++k;
      //较之前next数组求法，改动在下面4行
      if (p[j]!=p[k])
        next[j]=k;   //之前只有这一行
      else
        //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
        next[j]=next[k];
    }
    else
    {
      k=next[k];
    }
  }
}

int KmpSearch(char* s, char* p)
{
  int i=0;
  int j=0;
  int sLen=strlen(s);
  int pLen=strlen(p);
  while(i<sLen&&j<pLen)
  {
    //①如果j=-1,或者当前字符匹配成功（即S[i]==P[j]），都令i++j++
    if(j==-1||s[i]==p[j])
    {
      i++;
      j++;
    }
    else
    {
      //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]    
      //next[j]即为j所对应的next值      
      j=next[j];
    }
  }
  if(j==pLen)
    return i-j;
  else
    return -1;
}

char T[1000000+100],P[10000+100];
int f[10000+100];
int cnt;//统计出现的次数
void find(char *T,char *P,int *f)
{
    int n=strlen(T);
    int m=strlen(P);
    int j=0;
    for(int i=0;i<n;i++)
    {
        if(j && T[i]!=P[j]) j=f[j];
        if(T[i]==P[j]) j++;
        if(j==m) cnt++;
    }
}
void getFail(char *P,int *f)
{
    int m =strlen(P);
    f[0]=f[1]=0;
    for(int i=1;i<m;i++)
    {
        int j=f[i];
        while(j && P[i]!=P[j]) j=f[j];
        f[i+1] = P[i]==P[j]?j+1:0;
    }
}
int main()
{
    int K;
    scanf("%d",&K);
    while(K--)
    {
        cnt=0;
        scanf("%s %s",P,T);
        getFail(P,f);
        find(T,P,f);
        printf("%d\n",cnt);
    }
    return 0;
}