2

给定一个长度为 N(<=10^5) 的二进制字符串，我想找到字符串循环的长度。循环的长度最多为 1000 且至少为 1。

例子：

110110110110 循环长度为3（模式重复为110）

000000 循环长度为1（模式重复为0）

1101101101 循环长度为3（模式重复为110）

我试图理解弗洛伊德的循环检测算法，但我无法理解如何应用这个问题。

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

4

4 回答 4

3

这是这个问题的线性解决方案：

  1. 让我们计算给定字符串的前缀函数（就像在 Knuth-Morris-Pratt 的算法中一样）。

  2. 答案总是n - p[n]，其中n是给定字符串的长度，是字符串中位置p[i]的前缀函数的值i-th。证明：

    • 周期不小于n - p[n]。之所以如此，是因为对于任何时期k，s[i] = s[i + k]对于任何i。因此，n - p[n]至少是k由于前缀函数的定义。

    • 周期不大于k = n - p[n]。之所以如此，是因为s[i] = s[i + k]对于所有i由于前缀函数的定义，这意味着它k是一个句号。

于 2015-03-14T10:59:15.887 回答
1

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

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

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

编辑：正如 kaktusito 提到的，这行不通。但是，您可以使用 KMP 算法（但稍作修改）在从索引 2 开始的字符串S中查找字符串S。原始算法当然不会找到匹配项，但您可以对其进行修改，以继续搜索（即使您要查找的子字符串比原始字符串长）。然后，只要将子字符串匹配到原始字符串的末尾，您就会找到一个循环的长度（即使子字符串更长）。

于 2015-03-14T11:02:37.433 回答
1

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

例如，比较这两个图表：

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

和

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

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

您对示例 2 中的循环不感兴趣，只对“完整循环”感兴趣。

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

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

要检查是否存在 1 的循环，请将整数移位 1，并与自身进行比较：

000000000000
 000000000000
-yyyyyyyyyyy-
=> Matches!

110110110110
>110110110110
-ynnynnynnyn-
=> Nope

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

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

继续 3：

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

当然，您必须使用位算术来实现我刚刚描述的内容，这将由您决定。

于 2015-03-14T10:39:43.190 回答
1

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

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;
}
于 2015-03-14T10:59:32.227 回答