問題タブ [longest-substring]

ループを使用して、Python で関数を記述して、順序に関係なく、タンパク質の最長チェーンをソートするにはどうすればよいですか。この関数は、文字「A」、「C」、「G」、および「T」のみで構成される部分文字列を返します (同順位が他の要素と混同されている場合): '

最小限の長さのすべての一般的な一意の部分文字列 (実際にはパス) を見つける必要がある文字列のリストがあります。例：

この入力には、次の結果が必要です。

ご覧のとおり、一意のプレフィックスを持つ最小限の長さのパス (または部分文字列) が必要です。/a は、/a で始まるすべてのパスの最小部分文字列です。/d/e は、/d/e で始まるすべてのパスの最小部分文字列です。/g/h も同様です。

これの実用的なアプリケーションは、特定のファイルを含むパス ツリーのすべてのルートを見つけて、それらをさらに分析することです。次の例を検討してください。

/a/b/c/index.html

/a/b/index.html

/a/index.html

/d/e/f/index.html

/d/e/index.html

/g/h/index.html

index.html ファイルを含む最上位 (ルートに関して) のパスが必要だとします。その結果、「/a/index.html」、「/d/e/index.html」、「/g/h/index.html」が必要になります。

何か案は？「単純な」最長の共通部分文字列の問題には多くの理論と例がありますが、すべての共通の最長部分文字列を効率的に見つけるための解決策はまだ見つかっていません。

疑似コードを使用したソリューションは高く評価されます。

信号の位置合わせを行うためにレーベンシュタイン距離を実装しました。レーベンシュタインが、最適なソリューションであっても、私が望むソリューションを見つけられない場合があります。たとえば、次の文字列があります。

アルゴリズムは、文字列を一致させるために最初の 2 文字と最後の文字を削除する必要があることを認識する必要があります。

代わりに、次のものが見つかります。

したがって、必要以上に文字列を部分文字列に分割します。文字列を最小の部分文字列に分割するレーベンシュタイン距離の延長はありますか?

秋学期は動的計画法理論を勉強しましたが、ブラッシュアップしてさらに勉強を続けようと思っています。私は現在、この TopCoder 記事で述べられているように、LCS 問題への単純なアプローチを試みています:動的プログラミング

アルゴリズムは次のとおりです。

たとえば、文字列「ABCDE」と「DACACBE」の場合、最も長い共通サブシーケンスは「ACE」です。

ただし、正しい「ACE」ではなく、有効な部分文字列「ABE」を出力します。実装の順序の何が問題になっていますか?

最近、インタビューでこの質問をされましたが、 O(nlogn) ソリューションを提供できましたが、 O(n) のロジックが見つかりませんでした。誰かが O(n) ソリューションを手伝ってくれますか?

配列で、最も長い数列の長さを見つける

例 : 入力: 2 4 6 7 3 1 出力: 4 (1,2,3,4 は連続した位置になくてもシーケンスであるため)

ソリューションは、消費されるスペースの点でも現実的である必要があります。つまり、解は 10 億の数の配列であっても現実的でなければなりません

2 つの ArrayList を比較して、Java で最も類似しているサブセットを返したいと考えています。したがって、単一の値だけでなく、リストの一部を比較したいと考えています。

例：

最大サブセット:

2 番目に大きいサブセットは次のようになります。

これを効率的に行うにはどうすればよいですか? (2 つ以上の for ループを使用せずに)

keepAll() は機能しません。retainAll() は、最大のサブセットではなく、等しい値を返します。

出力として編集 したい、最大サブセットの前のリスト、最大サブセットの前のリスト、最大サブセットの後のリスト。例では、出力は次のようになります。