题解 | Coincidence

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

int dp[102][102];
//dp[i][j] s1前i个元素 s2的前j个元素的最大公共长度
//长度可为0到N,n+1个数,故dp数组长度应比字符长度大1

int main() {
	string str1, str2;
	cin >> str1 ;
	cin >> str2;
	//printf("%s\n", str1.c_str());
	//printf("%s\n", str2.c_str());
	// str1 = str1.c_str();
	// str2 = str2.c_str();
	int n = str1.length();
	int m = str2.length();
	for (int i = 0; i <= n; i++) {
		dp[i][0] = 0;
	}
	for (int j = 0; j <= m; j++) {
		dp[0][j] = 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			//前i个 s[0]-s[i-1]
			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]);
			}
		}
	}
	printf("%d\n", dp[n][m]);
	return 0;

}