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

常に最初のサイクルから開始すると、単純になります。次のようなことができます：

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 に答える
1

私がすでに持っている答えに加えて、別のアイデアがあります。まったく機能しない可能性があるため、間違っている場合は修正してください (Google でこのトピックについて何も見つかりませんでした)。ただし、ビットレベルでは機能しないため、32 または 64 のオーバーヘッドが発生します...

分析している文字列を と呼びましょうS。

おそらく、Knuth-Morris-Pratt アルゴリズム (線形時間で文字列内の部分文字列を見つける) を使用して、文字列内の を見つけるS( 2 回SS連結する) ことができます。Sもちろん、インデックス 2 から検索を開始する必要があります。アルゴリズムが返すインデックスは、サイクルの長さです。

編集: kaktusito が述べたように、これは機能しません。ただし、KMP アルゴリズムを使用して (ただし、少し変更して)、文字列S内のSインデックス 2 から始まる文字列を見つけることができます。元のアルゴリズムではもちろん一致するものは見つかりませんが、変更して検索を続けることができます (検索する部分文字列が元の文字列よりも長い)。次に、部分文字列を元の文字列の末尾に一致させるとすぐに、サイクルの長さがわかります (部分文字列が長くても)。

于 2015-03-14T11:02:37.433 に答える
1

Floyd のサイクル検出アルゴリズムは、わずかに異なる問題、つまりサイクルがあるグラフで使用されると考えられていますが、グラフ全体がサイクルである必要はありません。

例として、次の 2 つのグラフを比較します。

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

と

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

どちらにもサイクルがありますが、2 番目のものはノードの一部にしかサイクルがありません (つまり、1 はサイクルに表示されません)。

例 2 のようなサイクルには関心がなく、「完全なサイクル」のみに関心があります。

さらに、ビットを操作する場合、アルゴリズムは整数を操作する場合とは少し異なります (たとえば)。その理由は、1 回の比較だけで一度に多くのビットを比較できるからです (ビットの総数が 1 つの整数以下である限り)。

問題を解決する方法として考えられるのは次のとおりです。

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 に答える