[canonical] kmp

[Alice52]

kmp

1. concept

   • 前缀: 包含首字母且不包含尾字母的所有连续字母的集合, 比如 abc 的前缀有 a | ab
   • 后缀: 包含尾字母且不包含首字母的所有连续字母的集合, 比如 abc 的前缀有 c | bc

2. overview

   • 可以将时间复杂度从 n*m 优化到 m+n
   • 是搜索算法的一种: 解决字符串匹配问题
   • core: next 计算(最长相等前后缀数组)

3. next 数组求解: aabaabaabaaf => aabaabaaf

   • 初始化: j 前缀的尾字母(也是最长长度), i 循环变量
   • 前后缀相同: j=j+1
   • 前后缀不同: i 不变, j循环回退到j-1的位置
   • 赋值给 next

     void getNext (int* next, const string& s){
       next[0] = 0;
       int j = 0;
       for(int i = 1;i < s.size(); i++){
           while(j > 0 && s[i] != s[j]) {
               j = next[j - 1];
           }
           if(s[i] == s[j]) {
               j++;
           }
           next[i] = j;
       }
     }

4. kmp flow: while(i<m&&j<n)

   

5. full code

   void search(char text[], char p[]){
       int n=strlen(p);
       int *prefix=(int *)malloc(sizeof(int)*n);
           // 1. 
       prefix_table(p,prefix,n);
           // 2. 
       move_prefix_table(prefix,n);
       int m=strlen(text);
       int i,j;
           // 3. 
       while(i<m&&j<n){
           if(j==-1 || text[i]==p[j]){
               i++;
               j++;
           }
           else j=prefix[j];
       }
           return j>n;
   }