最长公共子序列
View Code #include#include using namespace std;const int maxn = 1000, maxm = 1000;int n, m, f[maxn][maxm];string a, b;void work(){ int i, j; f[0][0] = 0; for (i = 1; i <= n; i++) f[i][0] = 0; for (i = 1; i <= m; i++) f[0][i] = 0; for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) if (a[i - 1] == b[j - 1]) f[i][j] = f[i - 1][j - 1] + 1; else { f[i][j] = f[i - 1][j]; if (f[i][j - 1] > f[i][j]) f[i][j] = f[i][j - 1]; }}int main(){ //freopen("t.txt", "r", stdin); while(cin >> a >> b) { n = a.length(); m = b.length(); work(); cout << f[n][m] << endl; } return 0;}