定义问题
字符串匹配是这样一个问题： 对于两个包含且仅包含字母表∑中的字母的串P，T，计算出所有有效的**移进**s使得P[1..|P|] = T[s+1..s+|P|]。(|P|为P的长度)。
或者说：求出在什么位置P被T完全包含。
为了表达方便，定义m = |P|, n = |T|。P称为模式串，T称为匹配串。
朴素算法
朴素算法是一种显然的方法。直接给出伪代码：
Naive-Match (P, T)m = |P|, n = |T|for i = 1..n doif P[1..m] == T thenprint i" "朴素算法可以看成模式串紧贴匹配串滑动，尝试移进s = 1..n时能否匹配。大多数情况下，朴素算法已经可以解决问题。但是当数据极大（例如在很长的基因串中寻找一组基因）时，朴素算法的效率就显得差了。因此，科学家寻找到许多种优秀的匹配算法。这是一个常用算法时间对照表。
| 算法 | 预处理 | 匹配 |
|---|---|---|
| 朴素算法 | 0 | O((n-m+1)m) |
| Rabin-Karp | Θ(m) | O((n-m+1)m) |
| 有限自动机 | Θ(m∑) | Θ(n) |
| Knuth-Morris-Pratt | Θ(m) | Θ(n) |
所有的字符串算法都很麻烦（毕竟蒟蒻）。其中KMP用处比较广。在《算法导论》里KMP的介绍是以有限自动机为基础的，然而我又看不懂，gedao了半天才大致明白KMP的思想。
KMP算法
Quote：来自 zrO matrix67 Orz
假如，A=”abababaababacb”，B=”ababacb”，我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。
- 当A[i+1]=B[j+1]时，i和j各加一；什么时候j=m了，我们就说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。
- 当A[i+1]<>B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。我们看一看当 i=j=5时的情况。
详细内容参见 http://www.matrix67.com/blog/archives/115
个人理解
我是自己推导之后才看到上面大牛的解释，真的非常通俗。所以看不懂的同学可以去哪里膜拜一下。kmp算法实在比较恶心，虽然代码秘制煎蛋，不习惯推导的童鞋直接背下来就可以了。：（语言表达能力捉急）：。
ps：这里并没有使用图形辅助理解，个人认为这样更有利于理解kmp匹配原理。
kmp基于一个函数π，π表示有最大的t < i使P[1..t] = P[m-t+1..m]，则t = π。或者形式化地：
π[i] = max{t | P[1..t] = P[m-t+1..m] 且 t < i}证明一个结论，对于任意T[k-i+1..k] = P[1..i]，有：
π[i] = max{t | P[1..t] = T[k-t+1..k] 且 t < i}
用反证法，假设有π[i] < x < i使得P[1..x] = T[k-x+1..k]∵ P[1..i] = T[k-i+1..k]∴ T[k-x+1..k] = P[m-x+1..m]又 P[1..t] = T[k-x+1..k]∴ P[1..x] = P[m-x+1..m]∵ x > π[i], 根据定义，矛盾
原命题得证。这个结论将说明kmp不会错过正确解。
以及：
如果有s使T[k-s+1..k] = P[1..s]，
那么有T[k-π[s]+1..k] = P[1..π[s]]。
证明很简单，根据定义等量代换即可。这个结论将说明kmp不会找到错误解。
这些结论并不足以证明kmp的正确性，但是基本可以看出主要思想了。事实上，通过π可以省略许多无用的比较（基于第二个结论）。kmp匹配算法代码如下：
void kmp_match(int l) {// l是T的长度，pL是P的长度int q = 0;// 匹配的长度for (int i=1; i<=l; i++) {while (q > 0 && P[q+1] != T[i])q = pie[q];// 无法匹配下一位，找到可以部分匹配的最大部分，或者没有可以匹配if (P[q+1] == T[i])q++;// 下一位可以匹配if (q == pL) {// 找到printf("Shift %d >>> ", i-pL);q = pie[q];// 找下一个匹配位置}}
}计算匹配函数π的方法：
void kmp_init() {int k = 0;pie[1] = pie[0] = 0;// 第一位不可能找到匹配for (int i=2; i<=pL; i++) {while (k > 0 && P[k+1] != P[i])k = pie[k];// 同上，自己匹配自己罢了if (P[k+1] == P[i])k++;pie[i] = k;// 记录最长匹配}
}所谓自己匹配自己，就是π就是找到一对最大且相等的前缀和后缀，记录前缀出现位置。(基于定义)
kmp大概就是这样了，多思考就可以想通。。
kmp时间复杂度分析
kmp的复杂度为Θ(n)-Θ(m)，这里用摊还分析中的聚合分析法给出一个kmp_init复杂度分析例子。我们试图证明while循环的执行次数为O(n)。
k的初值为0，而k的值增长有且只有一个途径：10行的k++。由于for循环一次k最多加一，n-1次循环之后k最多为n-1呢。由于π < i，因此while循环只会使k减少，且一次至少减少1。而k < n-1，所以while的循环次数为O(n)。不难得出kmp_init的复杂度为Θ(n)。用这种方法也可以得出kmp_match的复杂度为Θ(m)。
linux下装逼代码
装逼专用，仅售998，到linux上看看效果吧。
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
char P[10005], T[10005];
int pL;
int pie[10005];
int readfln(char *str) {char c;int i = 0;str[0] = '\"';while (c = getchar()) {if (c!= '\n')str[++i] = c;else break;}return i;
}
void printfln(int shift,int l) {int beg = shift-5;if (shift <= 5)beg = 0;elseprintf("...");for (int i=beg+1; i<=shift; i++)putchar(T[i]);printf("\033[33m");printf("%s", P+1);printf("\033[0m");int end = shift+pL+5;if (shift+pL+5 > l)end = l;for (int i=shift+pL+1; i<=end; i++)putchar(T[i]);if (shift+pL+5 < l)printf("...");printf("\n");
}
void kmp_init() {int k = 0;pie[1] = pie[0] = 0;for (int i=2; i<=pL; i++) {while (k > 0 && P[k+1] != P[i])k = pie[k];if (P[k+1] == P[i])k++;pie[i] = k;}
}
void kmp_match(int l) {int q = 0;for (int i=1; i<=l; i++) {while (q > 0 && P[q+1] != T[i])q = pie[q];if (P[q+1] == T[i])q++;if (q == pL) {printf("Shift %d >>> ", i-pL);printfln(i-pL,l);q = pie[q];}}
}
int main() {pL = readfln(P);kmp_init();int l;while (l = readfln(T))kmp_match(l);return 0;
}参考资料：《算法导论》
