给定模式的前缀功能是否有可能具有这样的东西,
0 0 1 2 3 0 1 2 3 4 5 3 4 5
6 7 0 1 2
在 4 5 之后的上述前缀函数中,是否只有 6 或 0 的可能性?如果在 4 5 之后有可能出现例如 3(小于 5 且大于 0),如上述那样,那么模式应该如何。
我只能想到类似于这个的模式,
a b a b a b a b c a
0 0 1 2 3 4 5 6 0 1
谢谢。
给定模式的前缀功能是否有可能具有这样的东西,
0 0 1 2 3 0 1 2 3 4 5 3 4 5
6 7 0 1 2
在 4 5 之后的上述前缀函数中,是否只有 6 或 0 的可能性?如果在 4 5 之后有可能出现例如 3(小于 5 且大于 0),如上述那样,那么模式应该如何。
我只能想到类似于这个的模式,
a b a b a b a b c a
0 0 1 2 3 4 5 6 0 1
谢谢。
这是一个示例模式,其中 6 后链接 4 失败:
a b c a b c d a b c a b c a
0 0 0 1 2 3 0 1 2 3 4 5 6 4
您的特定示例是不可能的。当您开始从所需的前缀表构造字符串时,您会得到
0 0 1 2 3 0 1 2 3 4 5 3 4 5 6 7 0 1 2
a b a b a c a b a b a
表中对应于长度前缀的条目p
给出了该前缀的最宽边框的宽度b
,例如w
。下一个条目只能是w+1
(如果b
是可扩展的)、0(如果没有前缀匹配)或比b
.
因此,如果table[p]
包含 length-p 前缀的最宽边框的宽度(带有table[0] = -1
),table[p+1]
则为1+table[p]
, 1+table[table[p]]
, ...,之一1+table[table[...[table[p]]]] = 1 + table[0] = 0
。