fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define _nhatminh  int main()
  3. #define ll long long
  4. #define str string
  5. #define fir first
  6. #define sec second
  7. #define ld long double
  8. #define pb push_back
  9. #define MOD 100000009
  10. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define piint pair < int , int >
  13. #define piL pair < int , ll>
  14. #define pLL pair < ll , ll >
  15. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  16. using namespace std;
  17. const int Max_n=5*1e3 ;
  18. bool check[Max_n+3][Max_n+3];
  19. int dp[Max_n+3][Max_n+3] , f[Max_n+3];
  20. ll res = 1 ;
  21. void KT ( str a, str b){
  22. 	a = '*' + a ;
  23. 	b = '*' + b ;
  24. 	memset ( check , false , sizeof(check));
  25. 	memset ( dp , 0 , sizeof(dp));
  26. 	memset ( f , 0 , sizeof(f));
  27. 	int n = a.size() -1  , m = b.size() - 1 ;
  28. 	//fill ( check + 1 , check + n + 1 , 1 );
  29. 	for (int i = 1 ; i <= n ; i ++ )
  30. 		check[i][i] = true; 
  31. 	for (int d = 2 ; d <= n ; d ++ ){
  32. 		for (int i = 1 ; i <= n - d + 1 ; i ++){
  33. 			int j = i + d - 1 ;
  34. 			if ( d == 2 && a[i] == a[j] ) { check[i][j]= true; continue ;}
  35. 			if (a[i] == a[j] && check[i+1][j-1]) check[i][j] = true;
  36. 		}
  37. 	}
  38. 	// a - > b 
  39. 	for (int i = 1 ; i <= n ; i ++ )
  40. 		for (int j = m ; j >= 1 ; j -- ){
  41. 			if ( a[i] == b[j]) dp[i][j] = dp[i-1][j+1] + 2;  
  42. 		}
  43. 	for (int i = 1 ; i <= n ; i ++ ){
  44. 		for (int j = m ; j >= 1 ; j --)
  45. 			f[i] = max ( f[i] , dp[i][j]) , res = max ( res , 1ll*f[i]);
  46. 	}	
  47. 	for (int i = 1 ; i<= n ; i ++ ){
  48. 		for (int j = i ; j <= n ; j ++ )
  49. 			if ( check[i][j] ) {
  50. 				res = max ( res , 1ll*f[i-1] + j - i + 1 );
  51. 			//	cout << i+1 << ' ' << j << ' ' << f[i] << '\n';
  52. 		}
  53. 	}
  54. }
  55. void solve(){
  56. 	str a , b ; cin >> a >> b;
  57. 	KT ( a , b ) ; 
  58. 	reverse(ALL(b));
  59. 	reverse(ALL(a));
  60. 	KT(b,a);
  61. 	cout << res ; 
  62. }
  63. _nhatminh{
  64. freopen("GHEPXAU");
  65. ios_base::sync_with_stdio(0);
  66. cin.tie(0); cout.tie(0);
  67. int q=1;
  68. // cin >> q;
  69. while (q--)
  70. 	solve();
  71. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  72. return (0);
  73. }
  74.  
Success #stdin #stdout #stderr 0.03s 126104KB
comments (?)
stdin
copy 
ccc
ccc
stdout
copy 
6
stderr
copy 
Time elapsed 0.030653s.
https://ideone.com/g2jpbg
language:
C++14 (gcc 8.3)
created:
2 hours 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!