アルゴリズム-ダイナミックプランニング(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をとる.サブストリングの切り取り
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;



}