問題タブ [longest-substring]

さて、私の問題は次のとおりです。指定された 2 つの文字列間のより大きなシーケンスのサイズを返す必要があります。

現時点での私のコード:

いくつかの入力と期待される出力:

• abcdef cdofhij // 2 (ペア ("cd")
• TWO FOUR // 1 (文字「O」)
• abracadabra open // 0 (なし)
• ねえ、この Java はいいね Java は新しいパラダイム // 7 ("ava is ")

上記のすべての入力は私のコードで完全に機能していますが、場合によってはまだ失敗しています (文字が重複しているためか、わかりません)。

誤った出力の例:

• abXabc abYabc // 3 を出力するはずですが、4 を返します

だから、私は今立ち往生しています、どんな助けも大歓迎です。

町の名前を含む 2 つのベクトルがあり、どちらも異なる形式であり、水域 (水) の名前をそれぞれの国勢調査データ (町) に一致させる必要があります。基本的に、water の各行について、町で最もよく一致するものを知る必要があります。それらのほとんどには、city などの類似した単語が含まれているからです。私が目にするもう 1 つの問題は、あるデータ セットでは単語が大文字であり、別のデータ セットでは大文字ではないということです。これが私のサンプルデータです：

再帰と DP を使用して、2 つの文字列の最長共通部分文字列を見つけようとしています。Longest Contiguous subsequence について言及しているわけではないことに注意してください。したがって、2 つの文字列が

再帰とバックトラッキングを使用してこれを実行しようとしています。ただし、問題は、以下のような再帰を使用すると、呼び出しスタックの上位にあるフレームに+1が前もって追加され、来る文字が実際に連続要素であるかどうかを認識しないことです。したがって、上記の例では、「bcdf」が答えになります。

今のところ、以下のコードは私が思いついたものです。不一致を見つけるたびに、カウントを 0 にリセットする方法に注意してください。また、 int countという変数を使用して一致する文字の数を追跡し、int maxcountという変数を使用して、プログラム内の任意の時点で最大のものを記録します。以下の私のコード。

これはうまくいきます。ただし、コードについて気に入らない点がいくつかあります

1. フレーム間で比較するためのグローバル変数 (static int maxcount) の使用
2. これは実際の動的プログラミングまたはバックトラッキングではないと思います。下位フレームは出力を上位フレームに返さず、それをどうするかを決定するからです。

グローバル変数を使用せずにバックトラッキングを使用してこれを達成する方法について、ご意見をお聞かせください。

PS：行列を維持したり、次のようなことをしたりするなど、問題に対する他のアプローチを認識しています

M[i][j] = M[i-1][j-1]+1 if(str[i] == str[j])

目的は問題を解決することではなく、洗練された再帰/バックトラッキング ソリューションを見つけることです。

Ruby で最も長い回文問題を解決しようとしていますが、stackoverflow で答えを見つけました。

答え：

文字列に n 文字があるとします。最初に、文字列全体が回文であるかどうかを確認します。存在する場合は、文字列を返します。フィニ！そうでない場合は、長さ n-1 の 2 つの部分文字列のいずれかが回文であるかどうかを確認します。ある場合は、それを返します。そうでない場合は、長さ n-2 の部分文字列を調べます。文字列に少なくとも 1 つの文字が含まれている限り、最長の回文が検出されます。

しかし、私はこの行を理解するのに苦労しています:

何が

平均？

また、なぜこれが機能しないのですか？

これを実行すると、

しかし、["r"、"a"、"c"、"e"、"c"、"a" という条件を満たす最初の配列を検出したときに、ana が nil になる理由がわかりません。 、「r」]だから、これはanaにあるべきではないのですか？

この機能について助けが必要です。2 つの文字列の間で最も長い共通文字列を見つけようとしています。私が現在使用している関数は次のとおりです。

これは、約 600 語程度までの文字列でうまく機能します。それよりも単語数が多い文字列を比較しようとすると、system.outofmemoryexceptionがスローされ始めます。明らかに、これはメモリにかなりの打撃を与えています。この機能を微調整する方法はありますか、それともより合理化された別の方法がありますか?

私はこのアルゴリズムを初めて勉強しています。CLRS (15-4.6) は、O(n lg n) 時間で実行するアルゴリズムを作成するよう求めます。私が思いついたアルゴリズムは、O(n) で動作するようです。ウィキペディアでさえ O(n lg n) 時間かかるはずだと言っているので、私は何かを誤解しているに違いないと思います。( https://en.wikipedia.org/wiki/Longest_increasing_subsequence )
このアルゴリズム (Python で) が一般的に機能しない、O(n) でない、または質問に答えない理由を誰か教えてもらえますか??

最長の繰り返し部分文字列を見つけるためのアルゴリズムは次のように定式化されます 1)build the suffix tree 2)find the deepest internal node with at least k leaf children しかし、なぜこれが機能するのか理解できません。基本的に、このアルゴリズムが正しいのはなぜですか?また、このアルゴリズムを見つけたソースは、O(n) で繰り返される部分文字列を見つけるここで、n は部分文字列の長さです。これも私には明確ではありません!次のツリーを考えてみましょう。ここで、最も長く繰り返される部分文字列は「ru」であり、DFS を適用すると、5 ステップで検出されますが、2 では検出されません。あなたは私にこのことを説明しますか？ありがとう

画像

私が取り組んでいる問題はここにあります: http://practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/longestCommonSubsequence

基本的に、2 つの文字列が与えられ、最も長い共通部分列を見つけるように求められます。オンラインでソリューションを検索し、自分のソリューションと比較しましたが、コードにバグは見つかりませんでした。なぜまだうまくいかないのだろうか。

また、再帰的な方法を使用してこの問題を解決するように依頼されました

これが私のコードです：

そして、ここにすべてのテストケースがあります:

返される呼び出し値

「ABCDEFG」、「BGCEHAF」、「BCEF」

「彼女は売る」、「貝殻」、「貝殻」

"12345"、"54321 21 54321" "123"

「やんちゃ先生」「おいしいもも」「えちえちえちえち」

「マーティ」「ヘレン」「」

""、"ジョー" ""

「スージー」「」「」

「ACGGTGTCGTGCTA」、「CGTTCGGCTATCGTACGT」「CGGTTCGTGT」

私のコードでは、すべてのテスト ケースで StackOverFlow を取得しました。

Python は初めてのプログラミング言語で、手動でデータ構造を操作して遊んでみたいと思っていました。

私は最近、LCS問題を解決するための基本的なアルゴリズムを学んでおり、奇妙な理由で完全に把握していると自分自身を納得させることができない1行のコード以外に、それがどのように機能するかを理解しています。

これは、自分でうまく理解できなかった後、学ぶために使用してきたコードです。

編集 2:とにかく、整数の 2 つのリストの入力でこれを機能させるには? **元の質問を正しく理解していることがわかりましたが、**整数のリストでこれを機能させる方法を知っている人はいますか? S と T をカンマ区切りの値の文字列に変換してみましたが、これは一部の文字の一致に機能しましたが、それでもほとんどのテストケースではほとんど機能しませんでした。比較されるのは 2 つの文字列だけですが、コンマが含まれているため、なぜそうならないのかわかりません。

今、私の問題は次の行を理解することです: lcs_set.add(S[i-c+1:i-1])

部分文字列の長さを最長にするために、一致が見つかったときにカウンターがインクリメントされることを理解しています。したがって、簡単にするために、S = Crow で T = Crown の場合、最後の一致である w に到達すると、カウンターは 4 にインクリメントされ、i は S のインデックス 3 になります。

これは、次のように読むことを意味しますか: i (S のインデックス 3、W) - c (4)、つまり 3-4 = -1、つまり 3-4+1 = 0 (C で) と右側の場合スライスの: i(3) + 1 = 4(N、しかし明らかに含まれません)、つまり、S[0:4]、Crow、LCS_Setで終了しますか?

その場合、最新の一致した文字だけでなく、部分文字列全体をセットに追加する理由について混乱していると思いますか?

私が正しく理解している場合、現在一致している部分文字列のスライス全体でLCS_setを更新しているため、2 番目の一致である R の場合、カウンターは 2 になり、i は 1 になり、S[ となります。 1-2+1:i(1)+1]、したがって 1-2 = -1、-1 + 1 = 0(C) i(1)+1 = 2 まで (S[0:2 を残す) ]、または CR) であるため、毎回、セットは現在のインデックスだけでなく、部分文字列全体で更新されます。

それは実際には問題ではありません。これを正しく理解していることを確認したいだけです。

意見や、現在のロジックで誰かが見るかもしれないヒントをいただければ幸いです!!

編集：

Cの位置が現在のカウンター番号であることを完全に忘れていたことに気付きました。したがって、明らかに現在の最大一致番号でLCS_setを更新することはなく、現在の一致文字だけで更新することはできません。 LCS_Set を更新するには、部分文字列のスライスを取得する必要があります。前もって感謝します！