fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string x,y;
  5. int k,m,n;
  6. int dp1[1001][1001],dp2[1001][1001];
  7.  
  8. void longCS(){
  9. 	for (int i = 0; i <= m; i++)  {  
  10.         for (int j = 0; j <= n; j++) {  
  11.         if (i == 0 || j == 0)  
  12.             dp2[i][j] = 0;  
  13.         else if (x[i - 1] == y[j - 1])  
  14.             dp2[i][j] = dp2[i - 1][j - 1] + 1;  
  15.         else
  16.             dp2[i][j] = max(dp2[i - 1][j], dp2[i][j - 1]);  
  17.         }  
  18.     }  
  19. }
  20.  
  21. int f(int i,int j){
  22. 	if((m-i)<k||(n-j)<k)
  23. 		return 0;
  24.  
  25. 	if(dp1[i][j]!=-1)
  26. 		return dp1[i][j];
  27.  
  28. 	int c=0;
  29. 	while(i+c<m && j+c<n && x[i+c]==y[j+c])
  30. 		c++;
  31.  
  32. 	int ans = 0;
  33. 	if(c>=k){
  34. 		ans = dp2[m-i-c][n-j-c]+c;
  35. 		//cout<<"val =>"<<i<<","<<(m-i-c)<<" "<<j<<","<<(n-j-c)<<"\n";
  36. 		//cout<<c<<","<<dp2[m-i-c][n-j-c]<<"\n";
  37. 	}
  38. 	return dp1[i][j] = max({ans,f(i+1,j),f(i,j+1)});
  39. }
  40.  
  41. int main(){
  42. 	while(cin>>k){
  43. 		if(k==0) break;
  44. 		cin>>x>>y;
  45. 		m = x.length(),n=y.length();
  46. 		memset(dp1,-1,sizeof(dp1));
  47.  
  48. 		reverse(x.begin(),x.end());
  49. 		reverse(y.begin(),y.end());
  50. 		longCS();
  51. 		reverse(x.begin(),x.end());
  52. 		reverse(y.begin(),y.end());
  53.  
  54. 		cout<<f(0,0)<<"\n";
  55.  
  56. 	}
  57. 	return 0;
  58. }
  59.  
  60.  
Success #stdin #stdout 0s 7672KB
comments (?)
stdin
copy 
2
uxdnvxvnb
cjhdnhvwa
stdout
copy 
3
https://ideone.com/CweawA
language:
C++ (gcc 8.3)
created:
4 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!