fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int l1, l2;
  4. string s1,s2;
  5. int dp[5000][5000];
  6. int rec(int i, int j) {
  7. 	if(dp[i][j] != -1) return dp[i][j];
  8. 	if( i == l1 || j == l2) return 0;
  9. 	int ans = 0;
  10. 	ans += rec(i, j + 1);
  11. 	if(s1[i] == s2[j]) {
  12. 		ans +=1 + rec(i + 1, j + 1);
  13. 	}
  14. 	return dp[i][j] = ans;
  15. }
  16.  
  17. int main() {
  18. 	memset(dp, -1, sizeof(dp));
  19. 	cin >> s1 >> s2;
  20. 	l1 = s1.size();
  21. 	l2 = s2.size(); 
  22. 	cout << rec(0,0);
  23. }
Success #stdin #stdout 0.1s 100992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AEMNUw
language:
C++ (gcc 8.3)
created:
11 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!