最经典的问题，往往会产生最经典的算法，比如背包与递归，比如单源最短路径与Dijkstra，比如字符串匹配与KMP
给定一个字符串S，一个模式串P，请查找P在S中的位置
其实很简单，用一个i指向S，一个j指向P，只要S[i]==P[j]就说明现在S和P已经开始匹配上了，那么i++,j++继续匹配。如果到某一位S[i]!=p[j]则i回到开始匹配出+1，j归零,即i==i-j+1,j=0
代码实现如下：
int substring(char* s, char* p)
{
int sLen = strlen(s);
int pLen = strlen(p);
int i=0,j=0;
while(i<sLen && j<pLen){
if(s[i] == p[j]){
i++;
j++;
}
else{
i = i-j+1;
j = 0;
}
}
if(j == pLen)
return i-j;
return -1;
}
很显然，暴力解法有一个问题比如s="abcdefabcdeg";p="abcdeg"时，出现如下情况：
S a b c d e f a b c d e g
↑ ↑
P a b c d e g
↑ ↑
当S和P从a匹配到f/g的时候，终于发现不匹配了，暴力解法从b开始重新匹配是很浪费的，因为我们已经从a遍历到了f，其实信息已经表明从a到f中的以下位置都没有希望了
S a b c d e f a b c d e g
↑ ↑ ↑ ↑ ↑ ↑
所以接下来暴力解法中的5*6=30次比较其实是一种资源的浪费，这种最本质的原因是
因为你把"搜索位置"移到已经比较过的位置，重比一遍
一个基本事实是，当f与g不匹配时，你其实知道前面五个字符是"abcde"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。
其实如果P串中没有重复，比如上面这样，我们就应该直接从f后面开始匹配，因为没有重复，所以f前面a后面的任何一个字符不可能和a相等，显然是不需要匹配的
问题出在p如下面特性的时候：
P = "abcdefabcx"
如果匹配到最后一个x了，我们下一个匹配位置应该是第二个a开始，如下：
S a b c d e f a b c d e g
↑ ↑ ↑
P a b c d e f a b c x
↑ ↑
也就是当P串的头部在P串中再次出现的时候，说明我把P的头部移动到那个位置，还是可以由匹配机会的
S a b x d e f a b c d e g
↑ ↑
P a b c d e f a b c x
↑ ↑
当然，如果还没有匹配到那么后面，显然应该还是跳过所有已匹配位置
那么究竟应该跳到哪里继续匹配应该怎么算呢，显然这个值只与P串有关，与S串无关，我们可以推出一个字典DictP，来保存当前已经匹配的最后一个字符是P[i]时需要向后移动DictP[i]步
显然只有移动到某一位置i，S[0:i]的首尾有重叠，我们才需要考虑将i移动，使其首部正好移动到尾部的位置，继续匹配，假设首尾重叠部分有k个元素，显然我们应该移动i-k步，如果没有重叠元素，显然应该移动i步
根据每个S[0:i]的首位重叠情况，我们可以算出DictP[i]
代码实现：
int kmp(char* s, char* p)
{
int sLen = strlen(s);
int pLen = strlen(p);
char* dict = (char *)malloc(sizeof(char)*pLen);
dict[0] = 0;
for(int i=0,j=-1;i<pLen;i++){
if(-1 == j || p[i] == p[j]){
++i;
++j;
dict[i] = j;
}
else{
j = dict[j];
}
}
int i=0,j=0;
while(i<sLen && j<pLen){
if(s[i] == p[j]){
i++;
j++;
}
else{
j = dict[j];
}
}
if(j == pLen)
return i-j;
return -1;
}
[1]The Knuth-Morris-Pratt Algorithm in my own words
[2]字符串匹配的KMP算法-阮一峰
[3]KMP算法详解-Matrix67
[4]克努斯-莫里斯-普拉特算法-wiki