因此对于以下子字符串
1 2 3 4 5 6 7 8 9 10 11
a b c d a b c d a b x
哪个是前缀函数?我和我的一位 friend 计算了它,我们得到了不同的结果,我的是:
a b c d a b c d a b x
0 0 0 0 1 2 3 4 5 6 2
和他的:
a b c d a b c d a b x
0 0 0 0 1 2 3 4 1 2 0
如果我错了,为什么?
最佳答案
前缀表应该是:
a b c d a b c d a b x
0 0 0 0 1 2 3 4 5 6 0
所以给出的两个版本都不正确。
表格的最后一个条目
a b c d a b c d a b x
0 0 0 0 1 2 3 4 5 6 2
^
|
this one
为了正确起见,a b c d a b c d a b x
的长度为 2 的后缀(即 b x
)也必须是其长度为 2 的前缀,即 a b
> 相反。
如果前缀表中的条目不为零,则相应的前缀和后缀已在下表中标记:
a 0
a b 0
a b c 0
a b c d 0
a b c d a 1
-
=
a b c d a b 2
---
===
a b c d a b c 3
-----
=====
a b c d a b c d 4
-------
=======
a b c d a b c d a 5
---------
=========
a b c d a b c d a b 6
-----------
===========
a b c d a b c d a b x 0
关于algorithm - Knuth-Morris-Pratt 算法中的前缀函数计算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30410009/