kmp演算法中next數組的值怎麼求

㈠ 給出字元串在KMP演算法中的Next數組

逐個查找對稱串。

只要循環遍歷這個子串，分別看前1個字元，前2個字元，3個... i個 最後到15個。

第1個a無對稱，所以對稱程度0

前兩個ag無對稱，所以也是0

依次類推前面0-4都一樣是0

最後一個是0～3都一樣是0

前綴next數組的求解演算法：

void SetPrefix(const char *Pattern, int prefix[])

{

int len=CharLen(Pattern);//模式字元串長度。

prefix[0]=0;

for(int i=1; i<len; i++)

{

int k=prefix[i-1];

//不斷遞歸判斷是否存在子對稱，k=0說明不再有子對稱，Pattern[i] != Pattern[k]說明雖然對稱，但是對稱後面的值和當前的字元值不相等，所以繼續遞推

while( Pattern[i] != Pattern[k] && k!=0 )

k=prefix[k-1]; //繼續遞歸

if( Pattern[i] == Pattern[k])//找到了這個子對稱，或者是直接繼承了前面的對稱性，這兩種都在前面的基礎上++

prefix[i]=k+1;

else

prefix[i]=0; //如果遍歷了所有子對稱都無效，說明這個新字元不具有對稱性，清0

}

}

(1)kmp演算法中next數組的值怎麼求擴展閱讀：

設主串（下文中我們稱作T）為：a b a c a a b a c a b a c a b a a b b

模式串（下文中我們稱作W）為：a b a c a b

用暴力演算法匹配字元串過程中，我們會把T[0] 跟 W[0] 匹配，如果相同則匹配下一個字元，直到出現不相同的情況，此時會丟棄前面的匹配信息，然後把T[1] 跟 W[0]匹配，循環進行，直到主串結束，或者出現匹配成功的情況。這種丟棄前面的匹配信息的方法，極大地降低了匹配效率。

而在KMP演算法中，對於每一個模式串我們會事先計算出模式串的內部匹配信息，在匹配失敗時最大的移動模式串，以減少匹配次數。

㈡ kmp演算法中的next到底是什麼意思啊

先看看next數據值的求解方法
位序 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next值 0 1 1 2 2 3 1 2
next數組的求解方法是：
1.第一位的next值為0
2.第二位的next值為1
後面求解每一位的next值時，根據前一位進行比較
3.第三位的next值：第二位的模式串為b ,對應的next值為1;將第二位的模式串b與第一位的模式串a進行比較，不相等；則第三位的next值為1
4.第四位的next值：第三位的模式串為a ,對應的next值為1;將第三位的模式串a與第一位的模式串a進行比較，相同，則第四位的next值得為2
5.第五位的next值：第四位的模式串為a，對應的next值為2;將第四位的模式串a與第二位的模式串b進行比較，不相等；第二位的b對應的next值為1,則將第四位的模式串a與第一位的模式串a進行比較，相同，則第五位的next的值為2
6.第六位的next值：第五位的模式串為b，對應的next值為2;將第五位的模式串b與第二位的模式中b進行比較，相同，則第六位的next值為3
7.第七位的next值：第六位的模式串為c，對應的next值為3;將第六位的模式串c與第三位的模式串a進行比較，不相等；第三位的a對應的next值為1，則將第六位的模式串c與第一位的模式串a進行比較，不相同，則第七位的next值為1
8.第八位的next值：第七位的模式串為a，對應的next值為1;將第七位的模式串a與第一位的模式串a進行比較，相同，則第八位的next值為2
以上這種分析方法，位序是從1開始的，如果位序從0開始，剛第一位的next值為-1,後面的方法則相同

㈢ 那個，KMP演算法裡面 求模式串的next[]數組的方法看不懂； 有大神能詳細解釋一下不，看不懂哇

對於next[]數組
也就是子串的某個位置與自身的公共前綴的最後匹配位置。
這樣講可能有點抽象，說白了就是子串以該位置為最末位，自己和自己匹配的最長公共前綴。

而在進行next[]數組的第i個位置的求值時，該位置以前的所有next[]值已經求出，因此我們可以藉助之前求出的next[]值來更新此刻next[i]的值。

所以時間復雜度為O(2*m)

拿ababac來說：
第一步：
ababac
_ababac
i，j在一開始就失配，即next[2]=0。

第二步：
ababac
__ababac
i，j在第3位匹配，next[3]=1
同理：next[4]=2，next[5]=3，next[6]=4

在i=6，j=4時失配。

因此，將j=next[j]+1，i++，也就是匹配串後移。
即：
ababac
______ababac
此時，兩串失配，next[7]=0

求next[]數組代碼：
int next[100];
char str2[100];
void get_next()
{
int len2=strlen(str2);
int i=1,j=0;
while(i<len2)
{
if(j==0 || str2[i]==str2[j])
{
i++;j++;
next[i]=j;
}
else
j=next[j];
}
}

㈣ KMP演算法中的next數組如何計算

next[i]表示的是：
在第i個字元前面的i-1個字元裡面，
從開頭開始的1個字元與最後1個字元是否相等，若不是，則next[i]=0,否則繼續看下面；
從開頭開始的2個字元與最後2個字元是否相等，若不是，則next[i]=1,否則繼續看下面；
從開頭開始的3個字元與最後3個字元是否相等，若不是，則next[i]=2,否則繼續看下面；
……
就是這樣的判斷取值。
它的意思就是如果到了某個字元不匹配的情況時候，你就可以直接把模式串拖到從開頭開始的那next[i]個字元等於當前字元的前next[i]個字元的地方，這樣就少了很多重復的無效的比較和移動。

㈤ 涓測斺旀眰瑙next鏁扮粍鍜宯extval鏁扮粍

next鏁扮粍鐨勬眰瑙ｆ柟娉曪細 棣栧厛絎涓浣嶇殑next鍊肩洿鎺ョ粰0錛岀浜屼綅鐨刵ext鍊肩洿鎺ョ粰1錛屽悗闈㈡眰瑙ｆ瘡涓浣嶇殑next鍊兼椂錛岄兘瑕佸墠涓浣嶈繘琛屾瘮杈冦傞栧厛灝嗗墠涓浣嶄笌鍏秐ext鍊肩殑瀵瑰簲浣嶈繘琛屾瘮杈冿紝鑻ョ浉絳夛紝鍒欒ヤ綅鐨刵ext鍊煎氨鏄鍓嶄竴浣嶇殑next鍊煎姞涓1錛涜嫢涓嶇瓑錛岀戶緇閲嶅嶈繖涓榪囩▼錛岀洿鍒版壘鍒扮浉絳夋煇涓浣嶏紝灝嗗叾next鍊煎姞1鍗沖彲錛屽傛灉鎵懼埌絎涓浣嶉兘娌℃湁鎵懼埌錛岄偅涔堣ヤ綅鐨刵ext鍊煎嵆涓1銆

涓句緥錛

鍙﹁В錛堜笉鎯崇湅鍙璺寵繃錛夛細
奼俷ext鏁扮粍錛
鍏堟眰妯″紡涓睸 姣忎竴涓瀛楃﹀墠闈㈢殑閭ｄ釜瀛楃︿覆鐨勬渶澶у叕鍏卞墠鍚庣紑闀垮害錛屽皢榪欎竴緋誨垪闀垮害瀛樻垚涓涓鏁扮粍錛屾眰鍑烘潵鐨勬瘡涓闀垮害鍏跺疄灝辨槸鍜屾ā寮忎覆姣忎竴涓瀵瑰簲浣嶇疆涓婂仛姣旇緝鐨勪笅鏍
渚嬪傦細妯″紡涓叉槸 ABACABC 錛屽叾鏈闀垮叕鍏卞墠鍚庣紑闀垮害鏁扮粍涓猴細鎴戜滑灝嗘渶闀垮叕鍏卞墠鍚庣紑闀垮害璁頒綔 LCPSF 錛岀幇鍦ㄤ粠妯″紡涓茬涓涓瀛楃A寮濮嬶紝A鐨勫墠闈㈠瓧絎︿覆涓簄ull錛屾墍浠A涔嬪墠鐨勫瓙涓茬殑 LCPSF 鏄0錛涙潵鍒癇錛孊鐨勫墠闈㈠瓧絎︿覆鏄疉錛孉鏄鍗曠嫭鐨勫瓧絎︿笉瀛樺湪鍏鍏卞墠鍚庣紑錛屾墍浠ラ暱搴︿篃鏄0錛涙潵鍒癆錛孉鍓嶉潰鐨勫瓙涓叉槸AB錛 LCPSF 涓0錛涙潵鍒癈錛孋鍓嶉潰鐨勫瓙涓叉槸ABA錛 LCPSF 涓1錛涙潵鍒癆錛孉鍓嶉潰鐨勫瓙涓叉槸ABAC錛 LCPSF 涓0錛涙潵鍒癇錛孊涔嬪墠瀛愪覆涓篈BACA錛 LCPSF 涓1錛涙潵鍒癈錛孋鍓嶉潰瀛愪覆涓篈BACAB錛 LCPSF 涓2錛涘埌姝よ繖涓鏈闀垮叕鍏卞墠鍚庣紑鏁扮粍灝卞嚭鏉ヤ簡 [0,0,0,1,0,1,2] 灝嗚繖涓鏁扮粍浠庣浜屼釜鍊煎紑濮嬫瘡涓鍊煎姞1鍚庯紝寰楀埌 [0,1,1,2,1,2,3] 灝辨槸灝嗚佸拰瀛愪覆瀵瑰簲浣嶇疆姣旇緝鐨勪笅鏍囷紝鍗充負next鏁扮粍銆

鎺屾彙浜嗕笂闈㈡眰next鏁扮粍鐨勬柟娉曞悗錛屾垜浠鍙浠ヨ繀閫熸眰寰楁ā寮忎覆ABACABC鐨刵ext鏁扮粍涓篬0,1,1,2,1,2,3]錛岀幇鍦ㄧ戶緇奼傛ā寮忎覆ABACABC鐨刵ext-val鏁扮粍錛

奼傝Вnextval鏁扮粍鏄鍩轟簬next鏁扮粍鐨勶紝妯″紡涓叉瘡涓涓浣嶇疆鐨勫瓧絎﹀拰鍏秐ext鏁扮粍鍊肩粰鍑虹殑涓嬫爣鐨勫瑰簲浣嶇疆鐨勬暟浣滄瘮杈冿紝鐩哥瓑灝卞彇next-val涓瀵瑰簲鐨刵ext鏁扮粍鍊間綔涓哄綋鍓嶄綅緗瀛楃︾殑next-val鍊礆紝涓嶇瓑灝辯洿鎺ュ彇褰撳墠浣嶇疆瀛楃︾殑next鏁扮粍鐨勫間綔涓簄ext-val鐨勫箋

奼傝В姝ラわ細
next-val鏁扮粍絎涓涓鏁扮洿鎺ヤ負0銆
next-val絎浜屾暟錛氭ā寮忎覆絎浜屼釜瀛楃︿負B錛屽瑰簲鐨勪笅鏍囨暟緇勭浜屼釜鏁版槸1錛岄偅灝辨槸灝嗘ā寮忎覆鐨勭1涓瀛楃﹀拰B鐩告瘮杈冿紝A!=B,鎵浠ョ洿鎺ュ皢涓嬫爣鏁扮粍絎浜屼釜鏁1浣滀負next-val鏁扮粍絎浜屼釜鏁扮殑鍊
絎涓変釜鏁幫細妯″紡涓茬涓変釜瀛楃︿負A錛屽瑰簲涓嬫爣鏁扮粍絎涓変釜鏁頒負1錛屽彇鍏朵綔涓轟笅鏍囷紝鎵懼埌妯″紡涓茬1涓瀛楃︿負A錛孉=A錛岄偅鍙杗ext-val鐨勭涓涓鏁板仛涓簄ext-val絎涓変釜鏁扮殑鍊礆紝涔熷氨鏄0

涓句緥錛

next鏁扮粍鐨勭己闄蜂婦渚嬪備笅錛
姣斿備富涓叉槸"aabXXXXXXXXXXXXXX"錛屾ā寮忎覆"aac"
閫氳繃璁＄畻 "aac" 鐨刵ext鏁扮粍涓012錛屽綋妯″紡涓插湪瀛楃c涓婂け閰嶆椂錛屼細璺沖埌絎2涓瀛楃︼紝鐒跺悗鍐嶅拰涓諱覆褰撳墠澶遍厤鐨勫瓧絎﹂噸鏂版瘮杈冿紝鍗蟲ゅ勭敤妯″紡涓茬殑絎浜屼釜a鍜屼富涓茬殑b姣旇緝錛屽嵆 "aabXXXXXXXXXXXXXX"vs"aac"錛屾樉鐒禷涔熶笉絳変簬b銆傜劧鍚庝細璺沖埌1鎺ョ潃姣旓紝鐩村埌鍖歸厤鎴愬姛鎴栬呭尮閰嶅け璐ヤ富涓插悗縐諱竴浣嶃
鑰"aac"鐨刵extval鏁扮粍涓002 褰撳湪c澶遍厤鏃朵細璺沖埌2錛岃嫢榪樺け閰嶅氨鐩存帴璺沖埌0錛屾瘮next鏁扮粍灝戞瘮杈冧簡1嬈°
鍦ㄥ傛灉妯″紡涓插緢闀跨殑璇濓紝閭ｅ彲浠ョ渷鍘誨緢澶氭瘮杈冿紝鍥犳や嬌鐢╪extval鏁扮粍姣攏ext鏁扮粍楂樻晥銆

鍦ㄦā寮忓尮閰嶇殑KMP綆楁硶涓錛屾眰妯″紡鐨刵ext鏁扮粍鍊礆紙涔熺О涓篕MP綆楁硶涓澶辮觸鍑芥暟錛夊畾涔夊備笅錛

錛1錛夊綋j=1鏃訛紝涓轟粈涔堣佸彇next[1]=0?
絳旓細褰撴ā寮忎覆絎涓涓瀛楃︿笌涓諱覆涓鏌愬瓧絎︿笉鍖歸厤鏃訛紝涓諱覆鎸囬拡搴旂Щ鑷充笅涓瀛楃︼紝鍐嶅拰妯″紡涓茬涓涓瀛楃︽瘮杈冦傦紙next[1]=0 琛ㄧず妯″紡涓蹭腑宸叉病鏈夊瓧絎﹀彲涓庝富涓蹭腑褰撳墠瀛楃 s[i] 姣旇緝錛
錛2錛変負浠涔堣佸彇 max{k}錛宬鏈澶ф槸澶氬皯錛
絳旓細褰撲富涓蹭腑絎 i 涓瀛楃︿笌妯″紡涓蹭腑絎 j 涓瀛楃︿笉鍖歸厤鏃訛紝鑻ヤ富涓 i 涓嶅洖婧錛屽垯鍋囧畾妯″紡涓蹭腑絎 k 涓瀛楃︿笌涓諱覆涓絎 i 涓瀛楃︽瘮杈冿紝k 鍊煎簲婊¤凍鏉′歡 1<k<j錛屽苟涓 'p1...pk-1' == 'pj-k+1...pj-1'錛屽嵆妯″紡涓插悜鍚庣Щ鍔ㄧ殑璺濈諱負 k錛宬鍊煎彲鑳芥湁澶氫釜錛屼負浜嗕笉浣跨Щ鍔ㄤ駭鐢熶涪澶卞彲鑳界殑鍖歸厤錛宬瑕佸彇鏈澶у礆紝max{k}琛ㄧず縐誨姩鐨勬渶澶х殑璺濈伙紝k鐨勬渶澶у間負 j-1銆
錛3錛夊叾瀹冩儏鍐墊槸浠涔堬紵涓轟粈涔堝彇 next[j] = 1?
絳旓細浠ヤ笂涓ょ嶆儏鍐電殑涓嶅尮閰嶏紝涓諱覆鎸囬拡涓嶅洖婧錛屽湪鏈鍧忕殑鎯呭喌涓嬶紝妯″紡涓蹭粠絎 1 涓瀛楃﹀紑濮嬩笌涓諱覆絎 i 涓瀛楃︽瘮杈冿紝浠ヤ究涓嶄涪澶卞彲鑳界殑鍖歸厤銆

㈥ KMP演算法求next數組的問題

字元串如果是以0為下標的話next[7]是0，只有最後一位與第一位相等。

在第i個字元前面的i-1個字元裡面，

從開頭開始的1個字元與最後1個字元是否相等，若不是，則next[i]=0；

從開頭開始的2個字元與最後2個字元是否相等，若不是，則next[i]=1；

從開頭開始的3個字元與最後3個字元是否相等，若不是，則next[i]=2；

前綴next數組的求解演算法：

void SetPrefix(const char *Pattern, int prefix[])

{

int len=CharLen(Pattern);//模式字元串長度。

prefix[0]=0;

for(int i=1; i<len; i++)

{

int k=prefix[i-1];

//不斷遞歸判斷是否存在子對稱，k=0說明不再有子對稱，Pattern[i] != Pattern[k]說明雖然對稱，但是對稱後面的值和當前的字元值不相等，所以繼續遞推。

(6)kmp演算法中next數組的值怎麼求擴展閱讀：

kmp演算法完成的任務是：給定兩個字元串O和f，長度分別為n和m，判斷f是否在O中出現，如果出現則返回出現的位置。常規方法是遍歷a的每一個位置，然後從該位置開始和b進行匹配，但是這種方法的復雜度是O(nm)。kmp演算法通過一個O(m)的預處理，使匹配的復雜度降為O(n+m)。