首页 > 试题广场 >

已知串S='abaabcabc'，其next数组值为（）

[单选题]
已知串S='abaabcabc'，其next数组值为（） 
  • 011221234
  • 012312124
  • 011223123
  • 011223223
查看答案及解析
添加回答
邹吱吱头像 邹吱吱
]这道题采用手工求next数组的方法。
先求串S='abaabcabc'的部分匹配值：
'a'的前后缀都为空，最长相等前后缀长度为0。
'ab'的前缀{a}后缀{b}=，最长相等前后缀长度为0.
'aba'的前缀{a,ab}后缀{a,ba}={a}，最长相等前后缀长度为1.
......
依次求出的部分匹配值如下表第三行所示，将其整体右移一位，低位用-1填充，如下表第四行所示。
PM是部分匹配值（Partial Match）
编号 1 2 3 4 5 6 7 8 9
S a b a a b c a b c
PM 0 0 1 1 2 0 1 2 0
next -1 0 0 1 1 2 0 1 2
选项中next[1]等于0，故将next数组整体加1，答案选C
发表于 2023-05-14 21:10:25 回复(0)
提交观点

问题信息

难度：
1条回答 1241浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号