再帰と DP を使用して、2 つの文字列の最長共通部分文字列を見つけようとしています。Longest Contiguous subsequence について言及しているわけではないことに注意してください。したがって、2 つの文字列が
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 countという変数を使用して一致する文字の数を追跡し、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);
}
}
}
これはうまくいきます。ただし、コードについて気に入らない点がいくつかあります
- フレーム間で比較するためのグローバル変数 (static int maxcount) の使用
- これは実際の動的プログラミングまたはバックトラッキングではないと思います。下位フレームは出力を上位フレームに返さず、それをどうするかを決定するからです。
グローバル変数を使用せずにバックトラッキングを使用してこれを達成する方法について、ご意見をお聞かせください。
PS：行列を維持したり、次のようなことをしたりするなど、問題に対する他のアプローチを認識しています
M[i][j] = M[i-1][j-1]+1 if(str[i] == str[j])
目的は問題を解決することではなく、洗練された再帰/バックトラッキング ソリューションを見つけることです。