問題タブ [longest-substring]

次のような2つの文字列があります。

現在、最長の後置一致は

reを使用したソリューションは何ですか？

プレフィックスマッチで見つけた解決策は次のとおりです。

ここで見つけたスクリプトがあり、最も低い共通の部分文字列を探すときにうまく機能します。

しかし、私はいくつかの間違った/欠けている文字を許容するためにそれが必要です。必要な類似度のパーセンテージを入力するか、許容される欠落/間違った文字の数を指定できるようにしたいと思います。

たとえば、次の文字列を検索します。

大きな黄色いスクールバス

この文字列の内部：

彼らはその日の午後にbigyellowschokeバスに乗りました

これは私が現在使用しているコードです：

どんな助けでも大歓迎です。

アップデート

PHPのレーベンシュタイン関数は255文字に制限されており、検索している干し草の山のいくつかは1000文字以上です。

これがやや打ちのめされたトピックであることはわかっていますが、すでに回答されているものから得ることができる助けの限界に達しました.

これは、Rosalind プロジェクトの問題 LREP 用です。文字列内で最長の k ピート部分文字列を見つけようとしていますが、サフィックス ツリーが提供されています。各ノードからの子孫の葉の数で接尾辞テーブルに注釈を付け、子孫を持つノードを>=k見つけ、最後にそれらのノードの最も深いところを見つける必要があることはわかっています。理論的には、私は設定されています。

私は次のリソースから多くの助けを得ました (おっと、投稿できるのは 2 つだけです)。

• 文字列内で最も長い反復シーケンスを見つける
• 深さ優先検索 (Python)

ルートから各リーフへのパスを取得できますが、各ノードから子孫の数を取得できるようにツリーを前処理する方法がわかりません。小さなシーケンスで機能する別のアルゴリズムがありますが、指数関数的に複雑であるため、大きなものでは時間がかかりすぎます。DFS を使用すれば、線形の複雑さでタスク全体を実行できるはずです。このアルゴリズムが機能するには、長さ 40,000 までの文字列の最長の k-peat を 5 分以内に取得できる必要があります。

サンプル データを次に示します (1 行目: sequence、2 行目: k、サフィックス テーブル形式: parent child location length):

これからの出力はCATAC.

次のコード ( LiterateProgramsから変更) を使用すると、パスを取得できましたが、長いシーケンスでは各ノードのパスを解析するのにまだ長い時間がかかります。

私がやりたいことは、ツリーを前処理してdescendants >= k、深さを見つける前に要件を満たすノードを見つけることです。深さを計算する方法にもまだ到達していません。パス内の各ノードの深さを追跡し、合計するための辞書があると思いますが。

したがって、私の最初の最も重要な質問は、「ツリーを子孫の葉で前処理するにはどうすればよいですか?」ということです。

2 番目に重要でない質問は、「その後、深度をすばやく計算するにはどうすればよいか」です。

PS これは宿題などではありません。私は、計算上の課題で視野を広げようとしている生化学者です。

LCS の並列計算は、波面パターンに従います。これは、シリアル実装より遅い並列関数です。（対角線の数（並列）と行数（直列）が関係していると思います）

ここにシリアル関数があります

...テスト機能を追加すると思いました

n 文字のシーケンス S。各文字は、シーケンス内で何度も発生する可能性があります。同じ文字がすべて 1 か所にある S の最長部分列を見つけたいとします。

たとえば。S = aaaccaaaccbccbbbab の場合、そのような最長のサブシーケンス (回答) は aaaaaaccccbbbb ie= aaa__aaacc_ccbbb_b です。

言い換えれば、S に現れるアルファベット文字は、サブシーケンス内の 1 つの連続したブロックにしか現れない可能性があります。可能であれば、解を決定するための多項式時間アルゴリズムを与えてください。

比較可能なタイプの2つのものの間で最長共通サブシーケンスを見つけようとしています。アルゴリズムがダウンしていますが、再帰メソッド呼び出しを介してこれらのアイテムをリストに追加したいのですが、この方法で最後のアイテムをリストに追加する方法がわかりません。

これが私のコードです：

人工知能ユニットを構築しようとしています。私はまず感覚入力 (「観察」) を短期作業記憶リストに収集し、このリスト (「アイデア」) で見つかったパターンを継続的に形成し、それらのアイデアを長期保存メモリにコミットすることでこれを行う予定です。それらはかなりのサイズに達し、おそらく 7 つの連鎖した観測になります。ロックの「人間理解に関するエッセイ」に似た哲学者にとって、これは「タブラ・ラサ」ではありません。エンコードされた基本構造が必要です。

したがって、私の質問は次のとおりです。

この絶えず成長する観測文字列の最大の部分文字列を動的に統合または「パターン化」するための優れたアルゴリズムはありますか? たとえば、これまでに ABCDABCABC を与えられた場合、ABC のアイデア D と、他の 2 つの ABC のアイデアが必要です。次に、別の D が観察され、短期記憶に追加された場合、ABCD トークン、ABC トークン、および別の ABCD トークンが必要になります。任意の数の文字を追加した後に再実行する必要があるため、Shortest Common Substring は使用したくありません。簡単に検索/変更できるツリー構造を好むと思います。

これはまともな解決策のように見えますか? http://www.cs.ucsb.edu/~foschini/files/licenza_spec_thesis.pdf . 少なくとも、他のデータマイナーは楽しめると思います。

2 つの文字列の最長共通サブ シーケンスを実装しようとしています。私の方法は、ここに投稿されたものとは少し異なります。私は解決策に近づいていますが、ほとんど問題はありません。私を助けてください。

私の問題: 望ましい出力: メタリカ 現在の出力: etallica

私のコードは次のとおりです。

他の方法があることは知っていますが、簡単な方法を使用して実装しようとしました。問題点を指摘してください。

n 文字列の最も長い共通部分文字列を見つけて、その結果をプロジェクトで使用する必要があります。

すでにこれを行っているJavaの既存の実装/ライブラリはありますか?