fork(4) download
copy 
  1. /*
  2.     Template:
  3.     By Jugal :)
  4. */
  5.  
  6. #include <iostream>
  7. #include <vector>
  8. #include <stack>
  9. #include <queue>
  10. #include <map>
  11. #include <set>
  12. #include <utility> 
  13. #include <algorithm>
  14. #include <cstdio>
  15. #include <cmath>
  16. #include <cstdlib>
  17. #include <ctime>
  18. #include <cstring>
  19. #include <limits>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long ll;
  24. typedef vector <int> vi;
  25. typedef vector <vi> vii;
  26. typedef pair<int,int> pii;
  27.  
  28. #define pb push_back
  29. #define mp make_pair
  30. #define ff first
  31. #define ss second
  32. #define sz size()
  33. #define len length()
  34. #define rep(i,n) for(int i=0;i<n;i++)
  35. #define ref(i,a,n) for(int i=a;i<=n;i++)
  36. #define reb(i,n,a) for(int i=n;i>=a;i--)
  37. #define all(a) a.begin(),a.end()
  38. #define gi(n) scanf("%d",&n)
  39. #define pi(n) printf("%d",n)
  40. #define ps printf(" ")
  41. #define pn printf("\n")
  42.  
  43. char str[100000];
  44.  
  45. int main()
  46. {
  47.         int n,ans=0;
  48.         scanf("%d",&n);
  49.         scanf("%s",str);
  50.         int dp[2][100000];
  51.         int *prev=dp[0],*cur=dp[1];
  52.         ref(i,1,n) {
  53.                 ref(j,1,n) {
  54.                         if(str[i-1]==str[n-j]) cur[j]=1+prev[j-1],ans=max(cur[j],ans);
  55.                         else cur[j]=0;
  56.                 }
  57. 		int *temp;
  58.                 temp=prev;
  59.                 prev=cur;
  60.                 cur=temp;	
  61.         }
  62.         pi(n-ans);pn;
  63.         return 0;
  64. }
  65.  
Success #stdin #stdout 0s 3896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/aSZoMi
language:
C++ (gcc 8.3)
created:
9 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!