代码之家 › 专栏 › 技术社区 › R.. GitHub STOP HELPING ICE

此算法是否适用于查找字符串的句点?

algorithm string c

R.. GitHub STOP HELPING ICE · 技术社区 · 7 年前

答案 this question 引用Crochemore和Ryter的“文本算法”第340页中的线性时间算法来计算字符串的周期。然而,这是相当复杂的,根据双向算法中使用的最大后缀算法(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;
}

他们的版本采用了两种方式,从中可以得出最大后缀的周期,作为计算最大后缀的副作用。但是,除非我遗漏了一些东西,否则逻辑的有效性似乎并不依赖于最大后缀属性。

以上是否正确?如果没有,你能提供一个反例来说明它在哪里失败了吗?

1 回复 | 直到 7 年前

R.. GitHub STOP HELPING ICE 7 年前

即使在修复之后,一个反例是:

aabaaaba

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

该算法采用了两种方法,即计算最大后缀的周期作为查找最大后缀的副作用。做依赖于最大后缀属性。而不是 != 条件,它有单独的 > 和 < 条件,其中一个将替换候选后缀的开头,另一个将延长运行周期。不严格地说,上述情况不可能出现,因为 b > a ,在这种情况下,后缀将从 乙 或 a > b ,在这种情况下 aaa > aab . 我怀疑更详细地阅读这篇论文(这需要用一个索引来破译其糟糕的伪代码符号)将澄清其余的内容。

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

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