KMP算法是在给定的字符串中查找某一特定的字符串(我们称之为模式串(Pattern)).
时间复杂度是O(m+n):m是模式串的字符数，n是给定的目标串的长度。
在写自己见解之前，先给大家一个Martrix67大牛的关于KMP算法的一个链接
http://www.matrix67.com/blog/archives/115
我认为KMP算法的难点在于当匹配失效时，我们要将模式串的第几个字符与当前目标串的失效处进行比较。
我们用T来表示目标串，P(m)来表示有m个字符的模式串。
已知P[1...q] 与 T[s+1,s+2,....s+q]匹配。而P[q+1] 不等于T[s+q+1];
那么T[s+q+1]应该和P的哪个字符进行比较呢？
由P[1..q] = T[s+1,...s+q]对应相等，假设T[s+q+1]要和P[k+1]进行比较(我们是基于1的字符串，即第一个字符我们用1而不是0来表示它的下标。)
那么我们必须保证
P[1...k] = T[ s+q-k+1...,s+q].
因为在一定之前P[1...q] = T[s+1,...s+q];所以P[q-k+1...q] = T[s+q-k+1,...,s+q];
P[q-k+1,...,q]是P从q之前的k个字符，即P[q]的后面k字符。
P[1...k]是P的前k个字符。
所以当我们在P[q+1]和T[s+q+1]不匹配时，
我们就是找到最大的k，使得前k个字符和后k个字符相等。
代码如下：
long IndexOfSubString(LPCTSTR source,unsigned int start,LPCTSTR subStr)
{
long sourceLen = _tcslen(source);
long subLen = _tcslen(subStr);
long *helpArr = new long[subLen];
memset(helpArr,0,sizeof(long)*subLen);
helpArr[0] =-1;
long index(0);
long j(-1);
for(index=1;index<subLen;index++)
{
while(j>0 && subStr[index] !=subStr[j+1]) j = helpArr[j];
if(subStr[index] == subStr[j+1])
j++;
helpArr[index] = j;
}
j=-1;
for(index=start;index<sourceLen;index++)
{
while(j>-1&&source[index] !=subStr[j+1]) j=helpArr[j];
if(source[index] == subStr[j+1])
j++;
if(j==subLen-1)
return index-j;
}
delete[] helpArr;
return -1;
}