? ? 昨天看了一下用于字符子串查找的KMP算法，很巧妙，也很難編，程序不長(zhǎng)，理解起來(lái)可真是費(fèi)勁。因?yàn)橐肅語(yǔ)言來(lái)實(shí)現(xiàn)，所以書(shū)里KMP算法定義的next數(shù)組的求值方法需要改動(dòng)，因?yàn)镃語(yǔ)言里的字符串?dāng)?shù)據(jù)結(jié)構(gòu)并不是讓第一位存儲(chǔ)字符串長(zhǎng)度，而是直接保存了第一個(gè)字符，就是這樣一個(gè)小小的變化，可讓我傷透了腦筋，而且即便如此，對(duì)于算法的本質(zhì)也不算了解得很透徹，幾乎是在死命調(diào)試的情況下把程序給實(shí)現(xiàn)出來(lái)，里面是不是有bug也不敢確定，編程可真是件糾結(jié)的事，要是早些接觸就好了，可以靜靜的思考，不用背負(fù)著找工作的壓力來(lái)學(xué)習(xí)。

? ? 尋找字符串的子串，結(jié)果返回第一個(gè)匹配的子串首字符的位置，從0開(kāi)始。

1.先從簡(jiǎn)單算法開(kāi)始，簡(jiǎn)單算法主要是通過(guò)循環(huán)來(lái)實(shí)現(xiàn)。

? ? int Index( char* s, char* t, int pos ) ? ? ? ?/*s為目標(biāo)字符串，t為要尋找的字串，pos為s中的開(kāi)始位置*/

? ? {

? ? ? ? int slen, tlen;

? ? ? ? int i = pos, j = 0; ? ? ? ?/*使用i標(biāo)記s中的位置，使用j標(biāo)記t中的位置*/

? ? ? ??if( s == NULL || t == NULL )

? ? ? ? ? ? return -1;

? ? ? ? slen = strlen( s );

? ? ? ? tlen = strlen( t );

? ? ? ? if( tlen > slen || pos < 0 || pos > tlen - 1 )

? ? ? ? ? ? return -1;

? ? ? ? while( i < slen && j < tlen )

? ? ? ? {

? ? ? ? ? ? if( s[i] == t[j] )

? ? ? ? ? ? { ++i; ++j }

? ? ? ? ? ? else

? ? ? ? ? ? { i = i - j + 1; j = 0; } ? ? ? ?/*通過(guò)回溯i指針并將j重新指向起始位置*/

? ? ? ? }

? ? ? ? if( j >= tlen )

? ? ? ? ? ? return i - j;

? ? ? ? else

? ? ? ? ? ? return -1;

? ? }

2.首位匹配算法

類似簡(jiǎn)單算法，只是要先比較模式串t的首尾字符，首尾字符比較完后，再應(yīng)用簡(jiǎn)單算法比較中間字符

int Index_FL( char* s, char* t, int pos )

{

? ? int slen, tlen, patStart, patEnd;

? ? int i = pos, j, k;

? ??if( s == NULL || t == NULL )

? ? ? ? ? ? return -1;

? ? slen = strlen( s );

? ? tlen = strlen( t );

? ? if( tlen > slen || pos < 0 || pos > tlen - 1 )

? ? ? ? return -1;

? ? patStart = t[0];

? ? patEnd = t[ tlen - 1 ];

? ? while( i <= slen - tlen ) ? ? ? ?/*最后一個(gè)匹配位置為i = slen - tlen*/

? ? {

? ? ? ? if( s[i] != patStart ) ++i;

? ? ? ? else if( s[ i + tlen - 1 ] != patEnd ) ++i;

? ? ? ? else

? ? ? ? {

? ? ? ? ? ? k = 1; j = 1; ? ? ? ?/*用k來(lái)標(biāo)記s中的位置， 以i + 1為起點(diǎn)*/

? ? ? ? ? ? while( j < tlen - 1 && s[ i + k ] == t[j] ) ? ? ? ?/*對(duì)中間字符串應(yīng)用簡(jiǎn)單算法進(jìn)行匹配*/

? ? ? ? ? ? { j++; k++;?}

? ? ? ? ? ? if( j >= tlen - 1 ) ? ? ? ?/*由于末尾已經(jīng)檢測(cè)過(guò)相等，所以當(dāng) j = tlen - 1時(shí)表明匹配*/

? ? ? ? ? ? ? ?return i;

? ? ? ? ? ? else ? ? ? ?/*不匹配則i右移一位*/

? ? ? ? ? ? ? ? i++;?

? ? ? ? }

? ? }

? ? return -1;

}

3.KMP算法，主要差別就在于，之前在遇到不匹配的情況時(shí)都是回溯s字符串的i指針，使用該算法則保持i不變，回溯t字符串的j指針，并且通過(guò)將t數(shù)組的首尾字串的重合位數(shù)記錄在next數(shù)組中，在匹配過(guò)程中，通過(guò)next數(shù)組的值，來(lái)確定j指針的回溯位置。（說(shuō)的比較抽象，具體學(xué)習(xí)還是參看教材，我這里就是做個(gè)記錄便于以后復(fù)習(xí)或改進(jìn)O(∩_∩)O）

紅色部分是跟原先算法主要的不同之處

void get_next( char* t, int next[] ) ? ? ? ?/*若不存在k使得‘p0...pk-1’ = ‘pj-k...pj-1’，則令next[j] = 0（原先算法是令這種情況的next值為1）*/

{

? ? int tlen;

? ? int i = 1, j = 0;

? ? next[0] = 0;

? ? next[1] = 0;

? ? tlen = strlen( t );

? ? while( i < tlen )

? ? {

? ? ? ? if( t[i] == t[j] )

? ? ? ? { ++i; ++j; next[i] = j; }

? ? ? ? else

? ? ? ? {

? ? ? ? ? ? j = next[j];

? ? ? ? ? ? if( j == 0?) ? ? ? ?/*j == 0則代表next[i + 1] = 0，即不存在k使得‘p0...pk’ = ‘pi-k...pi’*/

? ? ? ? ? ? ? ? next[++i] = 0;

? ? ? ? }

? ? }

}

?

int Index_KMP( char* s, char* t, int pos )

{

? ? ? ? int slen, tlen, i, j;

? ? ? ? int next[100];

? ? ? ??if( s == NULL || t == NULL )

? ? ? ? ? ? return -1;

? ? ? ? slen = strlen( s );

? ? ? ? tlen = strlen( t );

? ? ? ? get_next( t, next );

? ? ? ? if( tlen > slen || pos < 0 || pos > tlen - 1 )

? ? ? ? ? ? return -1;

? ? ? ? i = pos; j = 0;

? ? ? ? while( i < slen && j < tlen )

? ? ? ? {

? ? ? ? ? ? if( s[i] == t[j] ) { ++i; ++j; }

? ? ? ? ? ? else

? ? ? ? ? ? {

? ? ? ? ? ? ? ? if( j == 0 ) ? ? ? ?/*當(dāng)s[i] != t[0]時(shí)直接將i移至下一位進(jìn)行比較*/

? ? ? ? ? ? ? ? ? ? ++i;

? ? ? ? ? ? ? ? else

? ? ? ? ? ? ? ? ? ? j = next[j];

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? if( j >= tlen )

? ? ? ? ? ? return i - tlen;

? ? ? ? else

? ? ? ? ? ? return 0;

}

? ??

轉(zhuǎn)載于:https://www.cnblogs.com/liangchao/archive/2012/09/20/2695233.html

總結(jié)

以上是生活随笔為你收集整理的KMP 算法——C的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。