アルゴリズム-ダイナミックプランニング(4)最長共通サブストリング-C++
動的計画(0)-文字列のインタリーブ構成、2次元テーブルはstr 1、str 2、aimの3つの文字列の関係を示しており、本編の最長共通サブ列はstr 1、str 2の2つの文字列の関係にすぎない.質問:2つの文字列を指定し、2つの文字列の最長共通サブ列を返します.例:str 1="1 AB 2345 CD",str 2="12345 EF"は,str 1[i]とstr 2[j]を共通サブストリングの最後の文字とした場合,共通サブストリングの最大長を表す「2345」の考え方を返す.2 Dテーブルはstr 1 row i行dp[i][0]str 2 col j列dp[0][j]のままである
手順:1.dp 1.1 dp[0][0]=trueを得る. 1.2.第一列col dp[i][0]=str 1[i]=str 2[0]1.3.1行目row dp[0][j]=str 2[i]=str 1[0]1.4.dp[i][j]1.4.1等しい前列+1 str 1[i]=str 2[j]dp[i][j]=dp[i-1][j-1]+1;1.4.2不等は0 str 1[i]!=str2[j] dp[i][j]=0; 2.dp値3をとる.サブストリングの切り取り
手順:1.dp 1.1 dp[0][0]=trueを得る. 1.2.第一列col dp[i][0]=str 1[i]=str 2[0]1.3.1行目row dp[0][j]=str 2[i]=str 1[0]1.4.dp[i][j]1.4.1等しい前列+1 str 1[i]=str 2[j]dp[i][j]=dp[i-1][j-1]+1;1.4.2不等は0 str 1[i]!=str2[j] dp[i][j]=0; 2.dp値3をとる.サブストリングの切り取り
using namespace std;
typedef vector> ivv;
//14:30
//dp +1
//1.dp[0][0]
//2.dp[i][0] str1[i] == str2[0] i=1 m_max)
{
m_max = dp[i][j];
}
}
}
}
void strArrCommon_main()
{
cout< m_max)
{
m_end = i;
m_max = dp[i][j];
}
}
}
//3.str1 str2
string strre;
strre=str1.substr(m_end - m_max + 1, m_end + 1);
cout << strre << endl;
}