已知串S=’aaab’,则next数组值为( )。
A. 0123 B. 1123 C. 1231 D. 1211
j=1时,next[j]=0;
PM存在时,next[j]=PM+1;
PM不存在时,next[j]=1.
为什么答案不是0120?
原题如下:
guge 回复 Syou: 题目问题,是这个字符串匹配另一个字符串,给chatgpt都问懵逼了你看看gpt的回答: 在计算字符串的 next 数组时,通常使用的是 KMP 算法(Knuth-Morris-Pratt 算法)。next 数组是用来优化 KMP 算法的一部分,用于指示当在匹配失败时,模式串应该回溯到哪个位置重新开始匹配。 对于给定的字符串 S = 'aaab',next 数组的值为 [0, 1, 2, 0]。下面是如何计算 next 数组的过程: 初始化 next 数组,next[0] 总是为 0。 从左往右遍历字符串,对于每个位置 i,计算 next[i]: 如果 i == 0,next[i] 保持为 0。 否则,找到以 i - 1 结尾的前缀子串和后缀子串的最长公共部分长度,并将其赋值给 next[i]。 如果 i - 1 结尾的前缀子串没有与之相等的后缀子串,则 next[i] 为 0。 下面是具体的计算过程: i = 0,没有前缀和后缀,next[0] = 0 i = 1,前缀子串为 'a',后缀子串为 'a',二者相等,next[1] = 1 i = 2,前缀子串为 'aa',后缀子串为 'aa',二者相等,next[2] = 2 i = 3,前缀子串为 'aaa',后缀子串为 'aaa',二者相等,next[3] = 3 最终得到 next 数组的值为 [0, 1, 2, 3]。
guge 回复 guge: 好吧记错了,这玩意就是0120
LEK 回复 Syou: next数组的定义是指以当前字符为结尾的最长相等前后缀的长度。根据这个定义,我们可以依次计算S的每个位置对应的next数组的值。 对于串S=’aaab’,计算next数组的过程如下: 在位置0,由于没有前缀和后缀,所以next[0] = 0。 在位置1,前缀为'a',后缀为'a',所以next[1] = 1。 在位置2,前缀为'aa',后缀为'a',所以next[2] = 1。 在位置3,前缀为'aaa',后缀为'a',所以next[3] = 1。 因此,最终得到的next数组为[0, 1, 1, 1],即1211。
linshuang 回复 guge: 我怎么算的还是0123啊
NEXT=K-1
A
用户登录可进行刷题及查看答案
登录后提交答案