fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long int
  5. #define pb push_back
  6. #define mp make_pair
  7. #define vi vector<int>
  8. #define ii pair<int,int>
  9. #define vii vector<ii>
  10. #define REP(i,a,b) for(int i = a;i <= b;++i)
  11. #define NREP(i,a,b) for(int i = a;i>=b;--i)
  12. #define boost ios_base::sync_with_stdio(0)
  13. #define mset(a) memset(a,0,sizeof(a))
  14. #define all(a) a.begin(),a.end()
  15. #define F first
  16. #define S second
  17. #define awesome main()
  18. ll gcd (ll a, ll b) {return ( a ? gcd(b%a, a) : b );}
  19. ll power(ll a, ll n) {ll p = 1;while (n > 0) {if(n%2) {p = p * a;} n >>= 1; a *= a;} return p;}
  20. ll power(ll a, ll n, ll mod) {ll p = 1;while (n > 0) {if(n%2) {p = p * a; p %= mod;} n >>= 1; a *= a; a %= mod;} return p % mod;}
  21.  
  22. const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
  23.  
  24. int LCS(string a,string b){
  25. 	int la=a.size(),lb=b.size();
  26. 	int dp[la+1][lb+1]={0};
  27. 	REP(i,1,la)	dp[i][0]=0;
  28. 	REP(i,1,lb) dp[0][i]=0;
  29.  
  30. 	REP(i,1,la){
  31. 		REP(j,1,lb){
  32. 			if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1;
  33. 			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  34. 		}
  35. 	}
  36. 	return dp[la][lb];
  37. }
  38.  
  39. int main() {
  40. 	// your code goes here
  41. 	int t;
  42. 	cin>>t;
  43. 	while(t--){
  44. 		string s;
  45. 		cin>>s;
  46. 		int n=s.size();
  47. 		int mn=INF;
  48. 		if(n==1){cout<<0<<endl;continue;}
  49.  
  50. 		REP(i,0,n-1){
  51. 			string r=s;
  52. 			r=r.substr(i,n-i);
  53. 			reverse(all(r));
  54. 			mn=min(n-2*LCS(s.substr(0,i),r) ,mn);
  55. 		}
  56. 		REP(i,0,n-2){
  57. 			string r=s;
  58. 			r=r.substr(i+1,n-1-i);
  59. 			reverse(all(r));
  60. 			mn=min(n-1-2*LCS(s.substr(0,i),r ),mn);
  61. 		}
  62. 		cout<<mn<<endl;
  63. 	}
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
3
a
KazuoK
mnrijaan
stdout
copy 
0
3
4
https://ideone.com/Yus4fE
language:
C++14 (gcc 8.3)
created:
6 years 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!