4

入力: 2 つの文字列 A と B。

出力: 繰り返され、重複しない部分文字列のセット

繰り返されるすべての文字列を見つける必要があり、それぞれが両方の (!) 文字列に少なくとも 1 回出現する必要があります。たとえば、

A = "xyabcxeeeyabczeee" および B = "yxabcxabee".

この場合、有効な出力は {"abcx","ab","ee"} になりますが、文字列 A でのみ発生するため、"eee" ではありません。

この問題は、「超極大反復」の問題と非常に関連していると思います。定義は次のとおりです。

最大反復ペア : S 内の同一のサブストリング alpha と beta のペアで、alpha と beta をいずれかの方向に拡張すると 2 つの文字列の等価性が失われるようなものです。トリプレット (位置 1、位置 2、長さ) として表されます。

最大繰り返し : 「S の最大ペアで発生する S の部分文字列」。例: S の abc = xabcyiiizabcqabcyrxar。注: 多数の最大反復ペアが存在する可能性がありますが、最大反復の限られた数しか存在できません。

超極大反復 「他の極大反復の部分文字列として決して発生しない極大反復」 例: abcy in S = xabcyiiizabcqabcyrxar.

すべての超極大反復を見つけるためのアルゴリズムは、「文字列、ツリー、およびシーケンスのアルゴリズム」で説明されていますが、接尾辞ツリーについてのみです。

1.) DFS を使用してすべての左多様なノードを見つける

S の各位置 i に対して、S(i-1) は左文字 i と呼ばれます。T(S) の葉の左文字は、その葉が表すサフィックス位置の左文字です。T(S) の内部ノード v は、v のサブツリー内の少なくとも 2 つの葉が異なる左文字を持つ場合、左多様化と呼ばれます。

2.) これらのノードに定理 7.12.4 を適用する:

左多様な内部ノード v は、v のすべての子が葉であり、それぞれが別個の左文字を持っている場合に限り、超最大反復 a を表します

文字列 A と B の両方を連結する必要があり、ステップ 2 で v の葉をチェックするときに、文字列 A と B から少なくとも 1 つの別個の左側の文字が必要であるという追加の制約も課す必要があります。これは、それらの位置を A の長さと比較します。位置 (左の文字) > 長さ (A) の場合、左の文字は A にあり、そうでない場合は B にあります。

サフィックス + lcp 配列でこの問題を解決するのを手伝ってくれませんか?

4

1 に答える 1