字符串匹配KMP算法学习笔记

本文适合以前学过KMP算法、想要温习和加深理解的读者阅读，不适合作为初学材料。

传统的字符串匹配算法

在传统的字符串匹配算法中，不论主字符串（T）和模式串（P，亦即关键字）已经匹配了多少位字符，只要T[i]和P[j]不相符，就得回炉重造倒回重新匹配，j和i都需要回溯。

但事实上，在T和P逐步匹配的过程中，我们完全可以得到一些有效的、可以避免重复工作的数据——

KMP

比如T的前5位和P的前5位已经匹配成功，在第6位时匹配失败，那么如果说在P的前5位（假设是ABCAB）里，有一个k值，使前k位和后k位的字符串可以相匹配（在这个例子里，k=2，前2位和后2位的字符串都是AB），则在 “T的前5位和P的前5位已经匹配成功” 的前提下，我们就可以不移动i，并且不必将j重设为0，而使j=k（指向k位字符串后的第一位，在这个例子中，即指向‘C’）。
这也就是KMP算法的核心思想。

注意，这里保持了i始终不回溯，但最终要求的结果（字符串P在T中首先出现的位置）是i-j。也就是说，如果单独把结果res当做一个变量的话，res是可能会回溯的。

于是KMP算法可以概括为：
不回溯T的i指针，在i和j不匹配的情况下将j重设为k。 k值由进行匹配之前对P字符串的计算得到，存储在数组next[p.length()]里。

代码

    #include<iostream>
    #include<string>
    using namespace std;
    int* GetNext(const string& p){

        int lenp = p.length();
       int*res = new int[lenp];

        int k = 0;
        *(res+0) = 0; 
        if (lenp > 1)*(res+1) = 0;

        for (int i = 1; i < lenp-1; i++){
            if (p[i] == p[k])*(res+i+1) = ++k;
            else {
                *(res+i+1)= 0;
                k = 0;
            }
        }
        return res;
    }

    void FindPosition(const string& t,const string& p){
        int pos;
        int lent = t.length();
        int lenp = p.length();
        int* next = new int[lenp];

        next = GetNext(p);
        //get ks

        bool suc = false;
        int j = 0;
        for (int i = 0; i < lent; ){
            if (t[i] == p[j]){ 
                if (j == lenp - 1){
                    suc = true;
                    pos = i-j+1;
                    break;
                }
                else{
                        i++; j++;
                }
            }
            else{
                if (j == 0)i++;
                else  j = next[j];
            }
        }

        //print result
        if (suc){
            cout << p << " is found at position " << pos << endl;
        }
        else{
            cout << "Not found." << endl;
        }
   }

    int main(){
        string t, p;
        cin >> t >> p;
        FindPosition(t, p);
        system("pause");
          return 0;
      }

这是我撸的渣代码，和教科书上简洁而优美的代码当然有云泥之别，甚至可能还有bug。
但就基本思路而言，与这段代码的冗长所共生的直白逻辑也许更让人易于理解，故在此贴上，聊作对前文不走心的解释的补偿。

最后再附上简洁而优美的教科书代码。

public static int[] getNext(String ps) {

char[] p = ps.toCharArray();

int[] next = new int[p.length];

next[0] = -1;

int j = 0;

int k = -1;

while (j < p.length - 1) {

   if (k == -1 || p[j] == p[k]) {

       next[++j] = ++k;

   } else {

       k = next[k];

   }

}

return next;

}