KMP 字符转哈希

KMP求取最长前后缀

比较子串

#include<stdio.h>
#include<string.h>
void makeNext(const char P[],int next[])//求相应的next数组 
 {
      int q,k;
      int m = strlen(P);
      next[0] = 0;
      for (q = 1,k = 0; q < m; ++q)
      {
         while(k > 0 && P[q] != P[k])
             k = next[k-1];
         if (P[q] == P[k])
         {
             k++;
         }
         next[q] = k;
     }
 }
 
 int kmp(const char T[],const char P[],int next[])
 {
     int n,m;
     int i,q;
     n = strlen(T);
     m = strlen(P);
     makeNext(P,next);
     for (i = 0,q = 0; i < n; ++i)//逐一往右扫描原串 
     {
         while(q > 0 && P[q] != T[i])//模式串跳动，找到最大的相同的前后缀 
             q = next[q-1];
         if (P[q] == T[i])
         {
             q++;
         }
         if (q == m)
         {
             printf("Pattern occurs with shift:%d\n",(i-m+1));
         }
     }    
 }
 
 int main()
 {
     int i;
     int next[20]={0};
     char T[] = "ababxbababacadabdfdsss";
    // char T[] = "ababxbababcdabdfdsss";
     //char P[] = "abcdabd";
     char P[] = "ababaca";//每次往前面已比较的地方找最大的相同的前后缀  当比较到c时，由于此时不相c字母不相等，则看已比较好的aba的最大的相同的前后缀为a，则只则比较它的后一个字母 
     printf("%s\n",T);
     printf("%s\n",P );
     // makeNext(P,next);
     kmp(T,P,next);
     for (i = 0; i < strlen(P); ++i)
     {
         printf("%d ",next[i]);
     }
     printf("\n");
 
     return 0;
 }