问题
问答题
令s=‘aaab’,t=‘abcabaa’,u=‘abcaabbabcabaacbacba’,分别求出它们的next值。
答案
参考答案:
解析:当位置j=1时,next[j]=0;当位置j>1时,next[j]的值为模式串的位置1到j-1构成的串中所出现的首尾相同的子串的最大长度加l,无首尾相同的子串时next[j]的值为1。本题答案如下表所示:
j | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
模式串s | a | a | a | b | |||
next[j] | 0 | 1 | 2 | 3 | |||
模式串s | a | b | c | a | b | a | a |
next[j] | 0 | 1 | 1 | 1 | 2 | 3 | 2 |
j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
模式串u | a | b | c | a | a | b | b | a | b | c |
next[j] | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 1 | 2 | 3 |
j | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
模式串u | a | b | c | a | b | a | a | |||
nect[j] | 4 | 5 | 3 | 2 | 2 | 1 | 1 | 2 | 1 | 1 |