KMP算法
待匹配表
| T | a | b | a | a | c | a | b | a | b | c | a | c |
最长公共前缀表
| 下标 | 0 | 1 | 2 | 3 | 4 | ||
| p | a | b | a | b | c | ||
| 前缀表 | -1 | 0 | 0 | 1 | 2 | ||
| -1 | 最长公共 | ||||||
| 0 | a | ||||||
| 0 | a | b | |||||
| 1 | a | b | a | a | |||
| 2 | a | b | a | b | ab | ||
| 0 | a | b | a | b | c |
匹配过程：
1、如果第一次在P:abab…匹配T:abaa…不成功，则b对应前缀为“1”，将P 中下标为“1”项 对应 T中当前匹配错误项，并以次类推直到正确为止，是一次匹配成功的过程。
一次匹配成功后：
2、如果还有其他可以匹配的字符串，则再次循环。如最后匹配成功的前缀为“2”，则将下表为“2”项 对应 T中当前匹配成功的最后一项，则循环步骤1.
前缀表“-1”为0前面一位。