fork download
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7. string x, y;
  8. int A[2][1001];
  9. while (cin >> x >> y )
  10. {
  11. for (int i = 0; i < 2; i++){
  12. for (int j = 0; j < 1001; j++){
  13. A[i][j] = 0;
  14. }
  15. }
  16. for (int i = 0; i < x.length(); i++){
  17. for (int j = 0; j < y.length(); j++){
  18. if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];
  19. else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);
  20. }
  21. }
  22. cout << A[(x.length() + 1) % 2][y.length()] << endl;
  23. }
  24. return 0;
  25. }
Success #stdin #stdout 0s 4392KB
stdin
AAABBB ABABAB
AXYAAZ CCCXCCCYCCCZCC
ABCDE EDCBA
stdout
4
3
1