试题-在KMP算法中，已知模式串为ADABCADADA,请写出模式串的next数组值？

题目

在KMP算法中，已知模式串为ADABCADADA,请写出模式串的next数组值？

A.0，1，1，2，1，1，2，3，4，3

B.0，1，1，1，2，1，2，3，4，3

C.2，1，1，2，1，1，2，3，3，4

D.1，2，3，2，1，1，2，4，4，3

上一题 下一题

解答

正确答案是 A

在包含Pj ( 0 <= j <= n - 1)的序列中，求出前缀后缀相同的最大长度
a d a b c a d a d a
0 0 1 0 0 1 2 3 2 3
在将该结果向右移动一位，并用-1填充第0位
-1 0 0 1 0 0 1 2 3 2
整体加1
0 1 1 2 1 1 2 3 4 3
因此选择A
KMP算法：分为模式串和主串

选A
A D A B C A D A D A
-1 0 0 1 0 0 1 2 3 2

点赞
收藏
分享
文章链接

C 0条回复评论

帖子还没人回复快来抢沙发

问题信息

分类：数据结构 - KMP

难度:

关联文章

史上最浅显易懂的KMP算法讲解：字符串匹配算法

最新校招难题刷题，快来进刷题群吧