位串中的循环检测

Question

给定一个长度为N(<=10^5)的二进制字符串，我想求出该字符串的循环长度。循环的长度将是最多1000 并且至少1.

示例：

110110110110 循环长度为3（图案重复为110）

000000 循环长度为1（花样重复为0）

1101101101 循环长度为3（图案重复为110）

我试图理解 Floyd's cycle detection algorithm 但我无法理解如何申请这个问题。

如何有效解决这个问题？（我想要一个在 O(NlogN) 或更好的时间内运行的算法）。

Answer 1

Floyd 的循环检测算法被认为用于稍微不同的问题，即图形，其中有循环，但不是整个图形都必须是循环。

例如，比较这两个图：

1 -> 2 -> 3 -> 4 -> 1 -> ...

和

1 -> 2 -> 3 -> 4 -> 2 -> ...

两者都有一个循环，但第二个只有部分节点有循环（即1没有出现在循环中）。

您对示例 2 中的循环不感兴趣，只对 "full cycles" 感兴趣。

此外，当您使用位时，您的算法将与您使用整数（例如）时略有不同。原因是您可以通过一次比较一次比较许多位（只要总位数 <= 一个整数）。

这里有一个可能的想法，你可以如何解决这个问题：

检查是否有1的循环，将整数移位一位，并与自身比较：

000000000000
 000000000000
-yyyyyyyyyyy-
=> Matches!

110110110110
>110110110110
-ynnynnynnyn-
=> Nope

所以000000000000有一个循环1，110110110110没有，所以继续测试2：

110110110110
>>110110110110
--nynnynnynn--
=> Nope

继续 3：

110110110110
>>>110110110110
---yyyyyyyyy---
=> Matches!

当然，你必须用位运算来实现我刚才描述的内容，我会把它留给你。

Answer 2

下面是这个问题的线性解法：

让我们计算给定字符串的前缀函数（类似于 Knuth-Morris-Pratt 的算法）。
答案总是n - p[n]，其中n是给定字符串的长度，p[i]是[=的前缀函数的值13=] 字符串中的位置。证明：
- 周期不小于n - p[n]。之所以如此，是因为对于任何时期 k，对于任何时期 i，s[i] = s[i + k]。因此，由于前缀函数的定义，n - p[n] 至少是 k。
- 周期不大于k = n - p[n]。之所以如此，是因为s[i] = s[i + k] for all i 由于前缀函数的定义，这意味着k是一个句点。

Answer 3

当它总是从第一个循环开始时，它会很简单。你可以这样做：

public int GetCycleLength(string binary, out int cycles)
{
    for (int i = 1; i < 1000; i++)
    {
        if (binary.Length % i == 0)
        {
            cycles = 0;
            do
            {
                cycles++;
                if (cycles * i > binary.Length - i - 1)
                {
                    break;
                }
            }
            while (binary.Substring(cycles * i, i) == binary.Substring((cycles + 1) * i, i));
            cycles++;
            if (cycles * i == binary.Length)
            {
                return i;
            }
        }
    }
    cycles = 0;
    return 0;
}

Answer 4

除了我已有的答案外，我还有一个想法。也许它根本不起作用，所以如果我错了请纠正我（我在 Google 上找不到关于这个主题的任何信息）。但是，它在位级别上不起作用，因此您有 32 或 64 的开销...

让我们称我们正在分析的字符串为S。

您可以使用 Knuth-Morris-Pratt 算法（以线性时间在字符串中查找子字符串）在字符串 SS 中查找 S（连接 S两次）。当然，您必须从索引 2 开始搜索。然后算法 returns 的索引就是循环的长度。

编辑：如 kaktusito 所述，这行不通。但是你可以使用 KMP 算法（但稍微改变一下）从索引 2 开始的字符串 S 中找到字符串 S。原始算法当然不会找到匹配项，但你可以修改它，继续搜索（即使你要查找的子字符串比原始字符串长）。然后，一旦将子串匹配到原始字符串的末尾，就已经找到了一个循环的长度（即使子串更长）。

位串中的循环检测

Cycle detection in bit-string

algorithm

cycle

bitstring