fork(6) download
copy 
  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4. int LCS[1024][1024];
  5. int LCSlen(string &x,int x1,string &y,int y1){
  6.   	for(int i = 0; i <= x1; i++)
  7.   	LCS[i][y1]=0;
  8.  
  9.   	for(int j=0;j<=y1;j++)
  10.   	LCS[x1][j]=0;
  11.  
  12.   	for(int i = x1 - 1; i >= 0; i--){
  13.   	for(int j = y1 - 1; j >= 0; j--){
  14.  
  15.   	LCS[i][j] = LCS[i+1][j+1];
  16.  
  17.   	if(x[i] == y[j])
  18.   	LCS[i][j]++;
  19.  
  20.   	if(LCS[i][j+1]>LCS[i][j])
  21.   	LCS[i][j]=LCS[i][j+1];
  22.  
  23.   	if(LCS[i+1][j]>LCS[i][j])
  24.   	LCS[i][j]=LCS[i+1][j];
  25.  
  26.   	}
  27.   	}
  28. return LCS[0][0];
  29. } 
  30.  
  31. int main()
  32. {
  33. string x;
  34. string y;
  35. cin >> x >> y;
  36. int x1 = x.length() , y1 = y.length();
  37. int ans = LCSlen( x, x1, y, y1);
  38. cout << ans << endl;
  39. return 0;
  40. }
Success #stdin #stdout 0s 7572KB
comments (?)
stdin
copy 
abababab
bcbb
stdout
copy 
3
https://ideone.com/hfLwnh
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!