题解 | Coincidence
Coincidence
https://www.nowcoder.com/practice/f38fc44b43cf44eaa1de407430b85e69
#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;
}
