KMP算法是在給定的字符串中查找某一特定的字符串(我們稱之為模式串(Pattern)).
時(shí)間復(fù)雜度是O(m+n):m是模式串的字符數(shù)，n是給定的目標(biāo)串的長(zhǎng)度。
在寫自己見(jiàn)解之前，先給大家一個(gè)Martrix67大牛的關(guān)于KMP算法的一個(gè)鏈接
http://www.matrix67.com/blog/archives/115
我認(rèn)為KMP算法的難點(diǎn)在于當(dāng)匹配失效時(shí)，我們要將模式串的第幾個(gè)字符與當(dāng)前目標(biāo)串的失效處進(jìn)行比較。
我們用T來(lái)表示目標(biāo)串，P(m)來(lái)表示有m個(gè)字符的模式串。
已知P[1...q] 與 T[s+1,s+2,....s+q]匹配。而P[q+1] 不等于T[s+q+1];
那么T[s+q+1]應(yīng)該和P的哪個(gè)字符進(jìn)行比較呢？
由P[1..q] = T[s+1,...s+q]對(duì)應(yīng)相等，假設(shè)T[s+q+1]要和P[k+1]進(jìn)行比較(我們是基于1的字符串，即第一個(gè)字符我們用1而不是0來(lái)表示它的下標(biāo)。)
那么我們必須保證
P[1...k] = T[ s+q-k+1...,s+q].
因?yàn)樵谝欢ㄖ癙[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個(gè)字符，即P[q]的后面k字符。
P[1...k]是P的前k個(gè)字符。
所以當(dāng)我們?cè)赑[q+1]和T[s+q+1]不匹配時(shí)，
我們就是找到最大的k，使得前k個(gè)字符和后k個(gè)字符相等。
代碼如下：
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;
}