またもや写経です。
- 2つの文字列の最大長を二次元配列で記憶する
- 文字一致ループの中で1つ前の最大長と比較していく
ということですが、この発想が出てこない。。
#include <iostream> #include <string> #include <algorithm> using namespace std; static const int N = 1000; static int c[N + 1][N + 1] = {}; static int lcs(string& X, string& Y) { const size_t m(X.size()); const size_t n(Y.size()); X = '\0' + X; Y = '\0' + Y; int lcs = 0; for (size_t i = 1; i <= m; i++) { for (size_t j = 1; j <= n; j++) { if (X[i] == Y[j]) { c[i][j] = c[i - 1][j - 1] + 1; } else { c[i][j] = max(c[i - 1][j], c[i][j - 1]); } lcs = max(lcs, c[i][j]); } } return lcs; } int main() { int n; cin >> n; string X, Y; for (int i = 0; i < n; i++) { cin >> X; cin >> Y; cout << lcs(X, Y) << endl; } return 0; }