問題タブ [longest-substring]

この後、私は完全に頭がおかしくなりました。小さなファイルと大きなファイルの 2 つのファイル間で最も長い共通部分文字列を見つける必要があります。どこから検索を開始すればよいかさえわかりません。これまでに持っているものは次のとおりです

これまでに行ったことは、各ファイルを文字列ビルダーに入れ、次に文字列に入れて二重スペースを取り除くことでした (MobyDick.txt でよく出てきました)。このコードを見つけました

このコードは役立ちますが、小さなファイルでのみ役立ちます。大きなファイルで実行するたびに、「メモリ不足: Java ヒープ領域」エラーが発生します。ヒープスペースの問題から逃れるには適切なアルゴリズムが必要ですが、Javaメモリを増やすことはできません。誰かが私を助けたり、正しい方向に向けたりできますか?

最近、ツリーを使用して最長共通部分文字列の問題を解決する方法を学んでいます。Wiki やその他のオンライン リソースから学んだ後、サフィックス ツリーを使用して最長の共通部分文字列を見つける必要があることがわかりました。

ウィキが言ったように：

文字列の集合の最も長い共通部分文字列は、文字列の一般化されたサフィックス ツリーを構築し、その下のサブツリー内のすべての文字列から葉ノードを持つ最も深い内部ノードを見つけることによって見つけることができます。

ジャスティンが言ったように：

(コンパクトな) サフィックス ツリーでは、すべての文字列からリーフ ノードを持つ最も深い内部ノードを見つける必要があります。同じ深さに複数のノードがある場合は、そのノードが表す文字列の長さを比較する必要があります。つまり、ABC、BC、C の深さはすべて同じなので、ABC、BC、C の文字列の長さを比較して、どちらが長いかを確認する必要があります。これは明らかにABCです。

ここで、すべての文字列から葉ノードを持つ最も深い内部ノードを見つけるプロセスは、実際にはすべての文字列からすべての接尾辞の中で最も長い共通の接頭辞を見つけるプロセスだと思いました。

ここで質問があります: すべての文字列のすべてのサフィックスを格納するプレフィックス ツリーを構築しないのはなぜですか? 次に、接頭辞ツリーを検索して、これらの接尾辞の最も長い共通接頭辞を見つけることができます。この2つの違いはわかりません。この問題を解決するためにプレフィックス ツリーの代わりにサフィックス ツリーを使用する理由を誰かに教えてもらえますか?

フォーラムからデータ フレームにスクレイピングされたテキスト メッセージのコレクションがあります。再現可能な例を次に示します。

私の考えは、メッセージに複数のメッセージを書いたすべての人について、同じ作成者のすべてのメッセージで見つかった最も長い共通サフィックスを見つけることです。他のすべての場合は、うまく劣化する正規表現の方法を見つけます。

関数 getLongestCommonSubstring のおかげで有望に見えるバイオコンダクタ パッケージ RLibstree を見つけましたが、関数を同じ作成者からのすべてのメッセージにグループ化する方法がわかりません。

2 つの異なる文字列の部分文字列を探しています。問題は次のとおりです。

2 つの文字列 x = X1...Xn および y = Y1...Ym が与えられた場合、最も長い共通部分文字列の長さと、インデックス i および j が XiXi+1...Xi+k の最大の k を見つけます。 -1 = YjYj+1...Yj+k-1. 時間 O(m*n) でこれを行う方法を示します。

誰かが私があまりにも長い間見てきたこの問題を手伝ってくれますか? 私はすでにこの問題のために部分空間をやろうとしましたが、結局間違っていました。どんな支援も喜んでいただければ幸いです！前もって感謝します！

編集：アップ

以下の文字列ではコードが正しく動作しません。

編集: 2 番目の文字列で 20 を 40 に変更すると、関数が正しく機能することに気付きました...

文字列の場合:

正常に動作します。問題はどこだ？

これが私のコードです：

このコードの出力 (最初の 2 つの文字列) は次のとおりです。

ただし、出力は次のようになります。

ボトムアップの動的プログラミングを使用して、2 つの String オブジェクトの LCS を記述しようとしています。スペースで適切に機能させることができますO(mn)。ただし、ご覧のとおり、前の列がすべて必要なわけではありません。そこで、スペースが になるように 2 列に収まるように変更しようとしましたO(m)。ただし、すべての入力に対して機能するわけではありません (たとえば、 this:abcabcおよびabcbcca)。ここで何が欠けていますか？ハードウェアではなく、コンテストでもありません。DPの練習。