习题12.4Coincidence(找到两个字符串的最长公共子串)（上海交通大学）

Coincidence(找到两个字符串的最长公共子串)（上海交通大学）

关键字：动态规划、最长公共字

关键需要处理好边界点，不然计算比较麻烦

#include<vector>
#include<string>
using namespace std;
//P236 习题12.4

int main() {
	//1. input data
	string str1, str2;
	cin >> str1 >> str2;
	int m = str1.size();
	int n = str2.size();
	//2.compute dp[i][j]
	vector<vector<int>> dp(m+1, vector<int>(n+1,0));
	for(int i = 1;i < m + 1; i++ ) {
		for (int j = 1; j < n + 1; j++) {
			if (str1[i-1] == str2[j-1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	} 
	cout << dp[m][n] << endl;
	return 0;
}