algorithm - より大きな循環文字列の最小循環サブ文字列

Question

私は、より大きな循環文字列で最短の循環サブ文字列の長さを返すアルゴリズムを見つけようとしています。

循環文字列は、「abababab」や「aaaa」など、2つ以上の同一の文字列を連結したものとして定義されます。

ここで、たとえば文字列T = "abbcabbcabbcabbc"の場合、パターン "abbc"のサイクルがありますが、最短の循環サブ文字列は"bb"になります。

Answer 1

複数回表示される部分文字列を探しているだけの場合：

文字列から接尾辞木を作成します。

接尾辞木を作成するときに、すべての部分文字列の繰り返しをカウントし、ノードでの出現回数に保存することができます。

次に、ツリーでBFS検索を実行し（短い文字列から長い文字列まで、階層化された検索が可能になります）、複数回発生した1より長い最初の部分文字列を見つけます。

全体の複雑さ：O（n）ここで、nは文字列の長さです

編集：

ルートからリーフへのパスは、Sのサフィックスと1対1の関係にあります

各ノードに1文字が含まれるツリーを実装できます。これにより、粒度が向上し、すべてのサブストリングを長さで表示できるようになります。

これがバナナの接尾辞木で、すべてのノードに1つの文字が含まれています。ここに、すべての部分文字列があることがわかります。

接尾辞木のアプリケーションセクションを見ると、まさにこの種のタスク、つまり部分文字列に関するものを見つけるために使用されていることがわかります。

ルートからの画像を見ると、すべてのサブストリングがルート（BFSリスト）から始まっていることがわかります。

b
a
n
ba
an
na
ban
ana
nan
bana
anan
nana
banan
anana
banana

Answer 2

あなたの例では、ジェネレーターを「abbc」と呼びましょう。つまり、より大きな文字列を取得するために繰り返す文字列です。

最初の観察は、いくつかの部分文字列を2回繰り返すことによって、より小さな文字列を作成する必要があるということです。

2 *ジェネレーターは循環的であるため、最小の文字列は2回繰り返されるジェネレーター（2 *ジェネレーター）よりも小さくする必要があることは明らかです。

ここで、より小さな循環文字列を検索する場合は、ジェネレータを3回使用して取得した文字列のみを考慮する必要があることに注意してください。実際、最小のものが存在しないが、それが4 *ジェネレーター内にある場合、少なくとも2つのジェネレーターにまたがる必要がありますが、最小のものではありません。

それでは、大きい方の文字列が3 * generator（または2 * generator）であると仮定しましょう。また、ジェネレーターの桁数が異なる場合、答えは2*generatorであることも明らかです。そうでない場合は、位置iとjにある大きな文字列で同じ文字のすべてのペアを見つけて、2 *（ji）の長さのaiで始まる文字列が循環しているかどうかを確認する必要があります。jiの昇順で試してみると、最初の成功後にやめることができます。