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. 	int n = a.size() -1  , m = b.size() - 1 ;
  25. 	//fill ( check + 1 , check + n + 1 , 1 );
  26. 	for (int i = 1 ; i <= n ; i ++ )
  27. 		check[i][i] = true; 
  28. 	for (int d = 2 ; d <= n ; d ++ ){
  29. 		for (int i = 1 ; i <= n - d + 1 ; i ++){
  30. 			int j = i + d - 1 ;
  31. 			if ( d == 2 && a[i] == a[j] ) { check[i][j]= true; continue ;}
  32. 			if (a[i] == a[j] && check[i+1][j-1]) check[i][j] = true;
  33. 		}
  34. 	}
  35. 	for (int d = 2 ; d <= n ; d ++ ){
  36. 		for (int i = 1 ; i <= n - d + 1; i ++ ){
  37. 			int j = i + d - 1 ;
  38. 			//ghep so xau con lien tiep cua x de dc xdx 
  39. 			if ( a[i] == b[j] ) dp[i][j] = dp[i+1][j-1] + 2 ;
  40. 			else dp[i][j] = 0 ;
  41. 			//cout << dp[i][j] << ' ' << i << ' ' << j<< '\n';
  42. 		}
  43. 	}
  44. 	for (int i = 1 ; i <= n ; i ++ ){
  45. 		for (int j = m ; j >= i ; j --)
  46. 			f[i] = max ( f[i] , dp[i][j]) ;
  47. 	}	
  48. 	for (int i = 1 ; i<= n ; i ++ ){
  49. 		for (int j = i ; j <= n ; j ++ )
  50. 			if ( check[i+1][j] ) {
  51. 				res = max ( res , 1ll*f[i] + j - i  );
  52. 			//	cout << i+1 << ' ' << j << ' ' << f[i] << '\n';
  53. 			}
  54. 	}
  55. }
  56. void solve(){
  57. 	str a , b ; cin >> a >> b;
  58. 	KT ( a , b ) ; 
  59. 	reverse(ALL(b));
  60. 	reverse(ALL(a));
  61. 	KT(b,a);
  62. 	cout << res ; 
  63. }
  64. _nhatminh{
  65. freopen("GHEPXAU");
  66. ios_base::sync_with_stdio(0);
  67. cin.tie(0); cout.tie(0);
  68. int q=1;
  69. // cin >> q;
  70. while (q--)
  71. 	solve();
  72. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  73. return (0);
  74. }
Success #stdin #stdout #stderr 0.01s 5828KB
comments (?)
stdin
copy 
axy
bxz
stdout
copy 
1
stderr
copy 
Time elapsed 0.006362s.
https://ideone.com/2dUfay
language:
C++14 (gcc 8.3)
created:
1 day 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!