fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int lcs(string s1, string s2){
  5.     int dp[s1.length() + 1][s2.length() + 1];
  6.     for (int i = 0; i <= s1.length(); i++)
  7.         dp[i][0] = 0;
  8.     for (int i = 0; i <= s2.length(); i++)
  9.         dp[0][i] = 0;
  10.     for (int i = 1; i <= s1.length(); i++){
  11.         for (int j = 1; j <= s2.length(); j++){
  12.             if (s1[i - 1] == s2[j - 1])
  13.                 dp[i][j] = 1 + dp[i - 1][j - 1];
  14.             else
  15.                 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
  16.         }
  17.     }
  18.     return dp[s1.length()][s2.length()];
  19. }
  20.  
  21. int main(){
  22.     string s1, s2; cin >> s1 >> s2;
  23.     cout << lcs(s1, s2);
  24.     return 0;   
  25. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
acbdads
asdaweaw
stdout
copy 
3
https://ideone.com/Au5VLp
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

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!