gpt4 book ai didi

c - 该算法对于查找字符串的句点是否正确?

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:39:29 25 4
gpt4 key购买 nike

this question 的回答引用 Crochemore 和 Rytter 的“文本算法”的第 340 页,使用线性时间算法来计算字符串的周期。然而,它相当复杂,以下改编自 Two Way 算法(由 Chrochemore 和 Perrin 提出)中使用的最大后缀算法,对于计算周期似乎是正确的:

size_t period_of(const char *x)
{
size_t j=1, k=0, p=1;
while (x[j+k]) {
if (x[j+k] != x[k]) {
j += k?k:1; // Previously: j += k+1;
k = 0;
p = j;
} else if (k != p) {
k++;
} else {
j += p;
k = 0;
}
}
return p;
}

他们的 Two Way 版本(从中改编)计算最大后缀的周期作为计算最大后缀的副作用。但是,除非我遗漏了什么,否则逻辑的有效性似乎并不取决于最大后缀属性。

以上说法正确吗?如果不是,您能否提供一个反例来说明它失败的地方?

最佳答案

修复后的反例是:

aabaaaba

在位置 3,算法首先开始匹配句点 3 匹配项的前缀。但是当它得到一个 a而不是 b在位置 5,它错误地将候选周期跳到 5,错过了实际周期 4。

Two Way 中的算法(从中改编)计算最大后缀的周期作为找到最大后缀的副作用,确实依赖于最大后缀属性。而不是 !=条件,它有单独的 ><条件,其中两者之一将替换候选后缀的开始,另一个将延长运行周期。不严格地说,不会出现上述这种情况,因为b > a ,在这种情况下,后缀将从 b 开始, 或 a > b , 在这种情况下 aaa > aab .我怀疑更详细地阅读这篇论文(这需要使用基于 1 的索引来破译其可怕的伪代码符号)将澄清其余部分。

不幸的是,我相当确信我所询问的算法是不可恢复的。

进一步注意,在示例中,a不必是单个字符。它可以是任意长的模式。这似乎排除了任何微不足道的线性时间修正。

关于c - 该算法对于查找字符串的句点是否正确?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53273495/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com