看了兩三天的KMP算法,一直看的迷迷糊糊的.現(xiàn)在把這些資料貼在這里...以備日后之需
?
1.串的模式匹配的改進(jìn)算法(這個(gè)網(wǎng)站對(duì)我的理解幫助很大,特別是右邊的那塊說(shuō)明部分,以前自己腦筋老是轉(zhuǎn)不過(guò)來(lái)) http://cist.dhu.edu.cn/kejian/%CA%FD%BE%DD%BD%E1%B9%B9%BE%AB%C6%B7%BF%CE%B3%CC/%D4%DA%CF%DF%D1%A7%CF%B0/text/chapter04/section3/c5.htm

2.KMP 算法的注記 http://www.cublog.cn/u/20/showart_136705.html?

3.KMP算法中推導(dǎo)next[],nextval[]--手記 http://jiasimon040510.t8log.ccut.cn/blog-htm-do-showone-tid-6983.html


4.算法原理：

在匹配過(guò)和中，當(dāng)主串中第i個(gè)字符與模式串中第j個(gè)字符“失配”時(shí)（s[i]!=t[j])，將模式串盡量向右移動(dòng)，讓模式串中第k（k<j)個(gè)字符與si對(duì)齊繼續(xù)比較,

要讓這個(gè)條件成立，那么在k之前的k個(gè)t字符[0 到 k-1]必須在i之前的k個(gè)s字符[i-k 到 i-1]相匹配即：

?? t[0, 1, 2...k-1] == s[i-k, i-k+1, i-k+2...i-1]???? ---(1)

而由之前的部分匹配成功的結(jié)果可知：
??
?? t[0, 1, 2...j-1] == s[i-j, i-j+1, i-j+2...i-1]???? ---(2)
==>
?? t[j-k, j-k+1, j-k+2...j-1] == s[i-k, i-k+1, i-k+2...i-1]?? --(3)

由(1)與(3)可得：

?? t[0, 1, 2...k-1] == t[j-k, j-k+1, j-k+2...j-1]???? ---(4)

求出k值,就是next[j]的值了

總之,相對(duì)我來(lái)說(shuō),算法不是很好懂.但是大家看到我這么笨的人到最后都能明白一二.大家就更沒(méi)有理由看不懂了,祝大家成功附上我的測(cè)試源碼:

#include? < iostream >

using ? namespace ?std;


void ?GetNext( char ?t[],? int ?next[])
{
???? int ?j? = ? 0 ;
???? int ?k? = ? - 1 ;
????next[j]? = ?k;
???? int ?tlen? = ?strlen(t);

???? while (j < tlen)
???? {
???????? if (k? == ? - 1 ? || ?t[j]? == ?t[k])
???????? {
????????????j ++ ;
????????????k ++ ;
???????????? if (t[j]? == ?t[k])
???????????? {
????????????????next[j]? = ?next[k];
????????????}
???????????? else
????????????????next[j]? = ?k;
????????}
???????? else
???????? {
????????????k? = ?next[k];
????????}
????}
}


int ?KMP( char ?s[],? char ?t[],? int ?pos,? int ?next[])
{
???? int ?slen? = ?strlen(s);
???? int ?tlen? = ?strlen(t);
???? int ?i? = ? 0 ;
???? int ?j? = ? 0 ;

???? while (i < slen? && ?j < tlen)
???? {
???????? if (j? == ? - 1 ? || ?s[i]? == ?t[j])
???????? {
????????????i ++ ;
????????????j ++ ;
????????}
???????? else
???????? {
????????????j? = ?next[j];????
????????}
????}

???? if (j? == ?tlen)
???? {
???????? return ?i - tlen;
????}
???? else
???????? return ? - 1 ;
}

int ?main?( int ?argc,? char ? ** argv)
{
????
???? char ?s[]? = ? " aaaabaabaaabaaabaaaaabaaabaaabaaabaaabaaabaaabaaabaaabaaabacb " ;
????
???? char ?t[]? = ? " aabaaa " ;

???? int ?next[ 20 ] = { 0 } ;
????GetNext(t,?next);????
???? for ( int ?i = 0 ;?i < 20 ;?i ++ )
????????cout << " next[ " << i << " ]:?? " << next[i] << endl;
????
????cout << KMP(s,?t,? 0 ,?next) << endl;
}