设目标串为s=”abcaabcaaabababaabca”, 模式串为p=”ababaaaba”。 则模式p的next数组的值是( ),nextval数组的值是( )。
时间: 2024-04-04 13:30:20 浏览: 17
模式串p的next数组的值为:-1, 0, 0, 1, 0, 1, 2, 2, 2。
解释:
- 第一个字符'a'的next值为-1,表示它没有前缀和后缀相同的部分;
- 第二个字符'b'的next值为0,表示它前面没有字符和它相同的前缀;
- 第三个字符'a'的next值为0,表示它前面没有字符和它相同的前缀;
- 第四个字符'b'的next值为1,表示它前面的字符"ab"和它的后缀"b"相同的长度为1;
- 第五个字符'a'的next值为0,表示它前面没有字符和它相同的前缀;
- 第六个字符'a'的next值为1,表示它前面的字符"ba"和它的后缀"a"相同的长度为1;
- 第七个字符'b'的next值为2,表示它前面的字符"aba"和它的后缀"ba"相同的长度为2;
- 第八个字符'a'的next值为2,表示它前面的字符"abab"和它的后缀"ab"相同的长度为2;
- 第九个字符'a'的next值为2,表示它前面的字符"ababa"和它的后缀"ba"相同的长度为2。
模式串p的nextval数组的值为:-1, 0, 0, 1, 0, 1, 2, 2, 2。
解释:
nextval数组的值是在next数组的基础上计算出来的,如果next[j]等于0或j等于0,则nextval[j]等于-1;否则,如果p[next[j]]等于p[j],则nextval[j]等于nextval[next[j]];否则,nextval[j]等于next[j]。
在本例中,因为p[0]等于p[3],所以nextval[3]等于nextval[next[3]],即nextval[3]等于1;因为p[1]不等于p[4],所以nextval[4]等于next[4],即nextval[4]等于0;因为p[2]不等于p[5],所以nextval[5]等于next[5],即nextval[5]等于1;以此类推,可以得到nextval数组的所有值。