問題タブ [longest-substring]

First Common Substring の実装を探しています

Longest Common Substring の実装を使用すると (句読点を無視すると)、「I think you are great」となりますが、この例では、最初に出現する共通部分文字列を探しています。

おそらく、最初の部分を取得できるすべての一般的な部分文字列のリストを生成して順序付けた実装です。

編集

比較されるトークンは完全な単語になります。単語全体の最初の最長シーケンスの貪欲な一致を探します。(接尾辞ツリーがアプローチで使用されたと仮定すると、ツリーの各ノードは単語になります)

txt ファイルがあるとします。各行は文字列を表します。トップ10の頻繁な部分文字列を見つける効率的な方法はありますか?

問題は、特定の文字列の部分文字列順列のサイズが大きすぎることです。N文字列の長さが与えられると、全C(N,0)+C(N,1)+..C(N,N)種類の部分文字列があります。

=============================================== [更新]

質問は「[a link] Algorithm to find the most common substrings in a string」と似ていますが、どちらも同じではありません。違いは、すべての文字列の中で上位 10 の頻度の高い部分文字列を見つけようとしたことですが、「[a link] Algorithm to find the most common substrings in a string to find the most common substrings in. 1 つの文字列" はローカル最適化のみです。

「[a link]文字列内で最も一般的な部分文字列を検索するアルゴリズム」のメソッドを使用すると、すべての文字列で 1 つの部分文字列はまれですが、最も頻繁になる可能性があります。たとえば、10 個の文字列があり、文字列が最も頻繁に str1 sub_str1 --4 回
str2 sub_str2 -- 4 回 ..
str10 sub_str10

各文字列の最も頻繁な部分文字列は異なり、それぞれが 4 回発生します。存在する sub_minor という名前の別の部分文字列がすべての文字列で発生し、1 回だけ発生する可能性があります。結果として、この sub_minor 文字列は、他のすべての sub_str 文字列を超える 10 で発生するため、最も頻繁に発生します。

すべての sub_str はすべてグローバル最適化ではなくローカル最適化のみであり、私の問題は主にグローバル最適化のためのものであり、「[リンク]文字列で最も一般的な部分文字列を見つけるアルゴリズム」とは異なります

Longest Common Substringのアルゴリズムを見つけました。これは通常、サイズのdynamic programming2 次元配列を使用して を使用して行われます。mxnmn

2 つの文字列に対して次の行列を作成します。

M[i][j] = 1 if s1[i]==s2[j] else 0.

たとえば、文字列が次の場合:abcxyおよびpqaabx

マトリックスは次のようになります。

1ここで、左上から右下の方向にあるすべての対角線で s の最大連続シーケンスを検索します。

この中の最大値が答えになります。

配列を明示的に使用せずに上記の操作を実行できます。時間の複雑さはまだO(M*N)です。したがって、メモリは必要ありません。

誰かが私が間違っているところを指摘できますか?

2 つの文字列aとbそれぞれがあります。の長さaは以上ですb。最長の共通部分文字列を見つける必要があります。複数の回答がある場合は、先に来る部分文字列を出力する必要がありますb(開始インデックスが最初に来るように)。

注: と の長さはa最大b10 ⁶です。

サフィックス配列を使用して最長の共通部分文字列を見つけようとしました（クイックソートを使用してサフィックスをソートします）。複数の答えがある場合、最長の共通部分文字列の長さに等しいすべての共通部分文字列をスタックにプッシュしようとしました。

知りたかったのですが、これを行うより速い方法はありますか？

以下を考えると、最長の共通部分文字列を見つけることができます：

[アウト]：

しかし、最長の共通部分文字列が英語の単語の境界を尊重し、単語を切り詰めないようにするにはどうすればよいでしょうか? たとえば、次の文:

s2 から単語を分割するため、望ましくないフォローを出力します。kappa

目的の出力は次のとおりです。

単語境界に関して最長の共通部分文字列を取得する ngram の方法も試しましたが、ngrams を計算せずに文字列を処理する他の方法はありますか? （答えを見てください）

同じコードの（長い）繰り返しブロックを抽出し、必要に応じてそれらのブロックとの間で通常の実行フローをジャンプさせようとしています。
これは、Hack と呼ばれる教育用アセンブリ言語で行われます。
それらのブロックを抽出するにはどうすればよいですか。
これが最長共通部分列問題のインスタンスであることは理解していますが、これにアプローチする方法がわかりません。
私は、これ、これ、およびその他のいくつかを見てきました-助けにはなりません。

ソリューションコース、関連する読み物、またはライブラリなど、あらゆる指針があれば大歓迎です。