KMP字符串匹配算法，效率真tm低，不够还算搞明白了，看在周末的份上，原谅自己了，呵呵。记录一下。
命题：设计算法，在字符串s中，从pos位置开始，查找第一个与目标字符串t相同的子字符串的起始位置。
kmp算法实现：第一步，预处理目标字符串t，求出t中每一个字符在与源字符串s中字符不等时移到的位置。方法是根据如下公式
next[0] = -1;
next[j] = max{k| 0<k<j && \"t0t1...t(k-1)\" == \"t(j-k)t(j-k+1)...t(j-1)\"};
next[j] = 0;
此公式可如下证明
首先，假设目标字符串下一次移动到k位置，那么这个k位置有什么特性呢，k之前的所有字符（k个，从0开始），应该和源字符串s中i位置前的k个字符相同，即：
\"t0t1...t（k－1）\" == \"s(i-k)s(i-k+1)...s(i-1)\"
而且，这时候，源字符串i位置之前的k个字符和目标字符串j位置之前的k个字符也相同，即：
\"t(j-k)t(j-k+1)...t(j-1)\" == \"s(i-k)s(i-k+1)...s(i-1)\"
那么得到如下结论
\"t0t1...t（k－1）\" == \"t(j-k)t(j-k+1)...t(j-1)\"
第二步，循环源字符串和目标字符串，如下吧，这段不好说了
while(s[i] != ’’ && t[j] != ’’)
{
if(j == -1 || s[i] == t[j]) //j==-1表示s[i]与t[0]不同
{
i++;
j++;
}
else
{
j = next[j];
}
}
if(t[j] == ’’)
return i-j;
else
return 0;
3COME考试频道为您精心整理，希望对您有所帮助，更多信息在http://www.reader8.com/exam/
