next數(shù)組的作用:當(dāng)模式串的第j個字符失配時，從模式串的第next[j]的繼續(xù)往后匹配

求模式串的next數(shù)組(手算)

next[1]

任何模式串都一樣，第一個字符不匹配時，只能匹配下一個子串，因此，往后，next[1]都無腦寫0

next[2]?

?任何模式串都一樣，第二個字符不匹配時，只能匹配模式串的第1個字符，因此，往后，next[1]都無腦寫1

next[3]??

在不匹配的位置前邊，劃一條分界線，模式串一步一步往后退，直到分界線之前"能對上"，或模式串能完全跨過分界線為止，此時j指向哪兒，next數(shù)組值就是多少

?

next[4]??

在不匹配的位置前邊，劃一條分界線，模式串一步一步往后退，直到分界線之前"能對上"，或模式串能完全跨過分界線為止，此時j指向哪兒，next數(shù)組值就是多少

next[5]

在不匹配的位置前邊，劃一條分界線，模式串一步一步往后退，直到分界線之前"能對上"，或模式串能完全跨過分界線為止，此時j指向哪兒，next數(shù)組值就是多少

next[6]

在不匹配的位置前邊，劃一條分界線，模式串一步一步往后退，直到分界線之前"能對上"，或模式串能完全跨過分界線為止，此時j指向哪兒，next數(shù)組值就是多少

?

總結(jié)

next[1]都無腦寫0?

next[2]都無腦寫1

其他next:在不匹配的位置前邊，劃一條分界線，模式串一步一步往后退，直到分界線之前"能對上"，或模式串能完全跨過分界線為止，此時j指向哪兒，next數(shù)組值就是多少

例題：

求模式串：ababaa的next數(shù)組

//求next[1]

??????->??????//i=1->i=2

ababaa-> ababaa?//j=0,第一個字符匹配失敗，只能匹配下一個子串，++i，++j

next[1]=0;

//求next[2]

a?????->a??????? //i=2

ababaa->? ababaa? //j=1//第一個字符匹配成功，第二個字符匹配失敗，i不動，j后退一步

next[2]=1;

//求next[3]

ab????->ab????//i=3

ababaa->? ? ababaa//第三個字符匹配失敗，模式串后退兩步，j指向1，j=1

next[3]=1

//求next[4]

aba???->aba???//i=4

ababaa->? ? ababaa//第四個字符匹配失敗，模式串后退，第一個字符a和主串第三個字符a匹配，j指向2，j=2

next[4]=2

//求next[5]

abab??->abab??//i=5

ababaa->? ? ababaa//第五個字符匹配失敗，模式串后退，字符串a(chǎn)b和主串第二個子串a(chǎn)b匹配，j指向3，j=3

next[5]=3

?

//求next[6]

ababa?->ababa?//i=6

ababaa->? ? ababaa//第六個字符匹配失敗，模式串后退，字符串a(chǎn)b和主串第二個子串a(chǎn)ba匹配，j指向4，j=4

next[6]=4

?例題2同理：