0
私は、再帰とDPを使用して2つの文字列の最長共通部分文字列を見つけようとしています。私は、最も長い連続サブシーケンスを指しているわけではないことに注意してください。したがって、2つの文字列がある場合再帰とDPを使用する最も長い共通部分文字列
String s1 = "abcdf"; String s2 = "bzcdf"
Longest Common Substring == "cdf" (not "bcdf").
Basically they have to be continuous elements
私は再帰とバックトラックを使用してこれをしようとしています。ただし、以下のような再帰を使用すると、+1がフレーム内で先頭に追加されます。これはコールスタックの上位にあり、来る文字が実際に連続する要素であるかどうかを認識しません。そして、上記の例では、 "bcdf"が答えになります。
public class ThisIsLongestCommonSubsequence_NotSubstring {
public static void main(String[] args) {
String s1 = "abcdgh";
String s2 = "abefgh";
System.out.println(fun(s1, s1.length()-1, s2, s2.length()-1));
}
static int fun(String s1, int i, String s2, int j)
{
if(i == -1 || j == -1)
return 0;
int ret = 0;
if(s1.charAt(i) == s2.charAt(j))
ret = fun(s1, i-1, s2, j-1) + 1;
else
ret = max(fun(s1, i-1, s2, j), fun(s1, i, s2, j-1));
return ret;
}
static int max(int a, int b)
{
return a>b?a:b;
}
}
今のところ、以下のコードは私が思いついたものです。私が不一致を見つけるたびに、カウントを0にリセットする方法に注意してください。 という変数を使用して一致する文字の数を追跡し、という変数を使用し、int maxcountという変数を使用して、プログラムの任意のポイントで最も高い値を記録します。下の私のコード。
public class LongestContinuousSubstringGlobalvariable {
static int maxcount = 0;
public static void main(String[] args) {
String s1 = "abcdghijl";
String s2 = "abefghijk";
fun(s1, s2, s1.length()-1, s2.length()-1, 0);
System.out.println("maxcount == "+maxcount);
}
static void fun(String s1, String s2, int i, int j, int count)
{
if(i == -1 || j==-1)
return;
if(s1.charAt(i) == s2.charAt(j))
{
if(count+1 > maxcount)
maxcount = count+1;
fun(s1, s2, i-1, j-1, count+1);
}
else
{
fun(s1, s2, i-1, j, 0);
fun(s1, s2, i, j-1, 0);
}
}
}
これは問題なく動作します。しかし、物事のカップルは、私が
- グローバル変数（静的int型MAXCOUNT）の使用は、フレームにわたって
- 私は、これは本当の動的プログラミングや後戻りはないと思います比較することが私のコードについては好きではありませんがあります下側のフレームはを返すではないので、上位のフレームに出力されます。上位のフレームは、それをどう処理するかを決定します。
グローバル変数を使用せずに、バックトラッキングを使用してこれを達成する方法について私にあなたの入力をお願いします。
PS：私は行列を維持するように、この問題に対する他のアプローチを認識していて、
M [i]の[J] = M [I-1]〜[J-1]のようなものをやって+1 if（str [i] == str [j]）
目的は、問題を解決するのではなく、エレガントな再帰/バックトラッキングソリューションを見つけることです。
[最長共通部分]（http://stackoverflow.com/questions/22319437/longest-common-substring）の可能性の重複 – Prune