从零开始养成算法·篇十：初探KMP

啥是KMP算法

KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。

KMP在字符串匹配上的应用

设|S| = n , |T| = m。首先考虑一个朴素算法，那就是将字符串 S 中的每一个长度为m的子串都与 T 进行一次匹配，失配后再匹配下一个，复杂度O(NM)。

手动模拟一下可以发现，上述做法中指向字符串 S 的指针和 T 的指针都有回退 ，但实际上我们并不需要发生回退，KMP算法就是通过防止指针回退来提升朴素算法效率的。

假设我们 S[i] 和 T[j+1] 发生了失配，如果我们知道 “T 中以 j 为末尾的真子串” 和 T[1, j] 的最长公共前缀的长度（假设为len，len一定小于 j ），那么显然 T[1, len] = S[i-len+1, i]；于是此时的 j = len，接着匹配即可。我们用nex数组（见下文）来存放 T 对应位置的“len”。

1.对字符串 T 进行自我“匹配”，求出一个数组 next；

2.对字符串 T 与 S 进行匹配，求出一个位置。

在朴素做法中，如果发生失配，则要将指向 S 串的指针回退到当前子串起始位置，并右移至下一个子串起始位置，同理指向 T 的指针也要回到起始位置。

1.默认next[1] = 0，代表从0开始遍历；
2.设计两个索引下标i=0,j=1，i用来求解回溯的地址，j用来模式串的遍历；
3.如果i=0，表示此时模式串没有出现相同字符，此时回溯地址为1即next[j] = 1，表示需要从模式串的第一个字符开始比较；
4.如果T[i] == T[j]表示模式串中出现了重复字符，则next[j] = i；
5.如果3和4都没有，表示从[i,j]这个范围没有出现回溯地址的变化，把i回溯到next[i]的位置。

void get_next(String T,int *next){
   int i,j;
   j = 1;
   i = 0;
   next[1] = 0;
   while (j < T[0]) {
       //printf("i = %d j = %d\n",i,j);
       if(i ==0 || T[i] == T[j]){
           ++i;
           ++j;
           next[j] = i;
       }else
       {
           i = next[i];
       }
   }
}

上诉方法在模式串存在字符重复的情况下，会有浪费对比的流程，可以考虑优化如下：

void get_nextVal(String T,int *nextVal){
   int i,j;
   j = 1;
   i = 0;
   nextVal[1] = 0;
   while (j < T[0]) {
       if (i == 0 || T[i] == T[j]) {
           ++j;
           ++i;
           if(T[i] != T[j])
               nextVal[j] = i;
           else
               nextVal[j] = nextVal[i];
       }else{
           i = nextVal[i];
       }
   }
}

int Index_KMP(String S,String T,int pos){
   
   int i = pos;
   int j = 1;
   int next[MAXSIZE];
   
   get_next(T, next);
   count = 0;
   while (i <= S[0] && j <= T[0]) {
       
       if(j == 0 || S[i] == T[j]){
           i++;
           j++;
       }else{
           j = next[j];
       }
   }
   
   if (j > T[0]) {
       return i-T[0];
   }else{
       return -1;
   }
   
}