1 Knuth-Morris-Pratt算法
简称KMP算法。已知字符源串Text和匹配目标串Pattern，设两者长度分别为n和m(n>=m)，意图在源串Text中判定Pattern是否出现以及出现的次数，即所谓的匹配。约定s[a--b]代表字符串s的子串{s[a],s[a+1]....s[b]}。
KMP算法的精髓即为，利用已经匹配的子串的信息，避免不必要的尝试。如下：
index：0 1 2 3 4 5 6 Text：b a b a b c b a b a b a c b d........ Pattern：a b a b a c b index：0 1 2 3 4 5 6
在上图的匹配进程中，从Text[1]开始匹配，已经匹配成功4个字符，Text[5]与Pattern[4]的位置不匹配。按照朴素匹配算法的思路，应该是匹配失败，继而从Text[2]开始，从头匹配Pattern。但可以发现，已经匹配的子串“abab”的后两位字符实际上是与Pattern的前2位字符匹配的。也就是说，我们没有必要从Text[2]开始去匹配Pattern[0]，而是直接判断Text[5]是否匹配Pattern[2]。即匹配进程变成下面的情形：
index： 0 1 2 3 4 5 6 7 8 9 Text： b a b a b c b a b a b a c b d Pattern： a b a b a c b index： 0 1 2 3 4 5 6
定义Pattern的匹配控制一维矩阵P，长度与Pattern相同。P[j]的值这样获得，在字符串匹配的过程中，已知Text[s--s+j]与Pattern[0--j]匹配成功，但是Text[s+j+1]！=Text[j+1],那么在匹配成功的Text[s--s+j]中，通过移动Pattern，P[j]==仍旧匹配到Pattern的最大索引位。如上面的情形，s=1,j=3,仍旧匹配的最大索引位为1,故p[3]=1。这其实是利用了Pattern中出现相同子串的特性,对于任意给定的Pattern，直观上可以这样获得p[j]，找出中最大的m，m满足Pattern的子串p[0--j]的前m位子串和后m位子串的相同，那么p[j]=m-1;对于Pattern=a b a b a c b，对应的P[7]={-1,-1,0,1,2,-1}，-1的含义为：当前的Text[i]需要匹配Pattern[j+1]即Pattern[0]开始匹配。 这就是KMP精髓所在，利用已经匹配的信息，控制Text当前的字符T[s+j+1]需要去匹配Pattern的索引位置。
产生P：
int* preFix(string Pattern){ int *p = new int[Pattern.size()]; p[0] = -1; int j = -1; for (int i = 1; i -1 && Pattern[i] != Pattern[j + 1]) j = p[j]; if (Pattern[i] == Pattern[j + 1]) j = j + 1; p[i] = j; } return p;} 可以看出，这实际上式Pattern自我匹配过程。在for循环的if语句中,若j>-1，一旦Pattern[i]==Pattern[j+1]，则P[i]=j+1。若j=-1,则P[i]=-1。
Text与Pattern的匹配代码：
void KMPmatch(string Text, string Pattern){ int *p = new int[Pattern.length()]; p = preFix(Pattern); int count = 0; int j = -1; for (int i = 0; i -1 && Text[i] != Pattern[j + 1]) j = p[j];// if (Text[i] == Pattern[j + 1]) j = j + 1;//TextPattern[0--j+1] if ((j + 1) == Pattern.length())// { cout << "" << ++count << """" << i - j << endl; j = p[j]; }// } delete p;} 从宏观的角度，KMP避免了朴素匹配算法中，需要在Text中一一挪动开始匹配位置的情形，它利用已经匹配的字符，明确了有些偏移是无效且没必要的，并且直接跳转至Text中可能完全匹配的匹配起始位，匹配起始位置的偏移并没有明确反映在程序中，而是通过更新当前字符Text[i]需要匹配的Pattern的索引位来体现的。例如在上面的例子中，匹配起始位为T[2]没有意义，T[3]才有意义，匹配起始位置为T[3]实质是通过将当前待匹配的字符Text[5]需要去判断是否匹配Pattern的索引位置，切换为2，即判断Text[i]？=Pattern[2]来体现的。 KMP算法适用连续字符串的匹配。对于某些问题，比如寻找包含Pattern所有字符的Text中的最小子串并不适用。预处理时间为Θ(m)，匹配时间为Θ(n),均为线性。
以上为个人理解，可以参考