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)。