Advertisement
Guest User

Untitled

a guest
Oct 24th, 2017
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.00 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define pii pair <int, int>
  7. #define pb push_back
  8. #define f first
  9. #define s second
  10. #define mp make_pair
  11. #define sz(x) (int)x.size()
  12. #define forit(it, v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
  13. #define sqr(x) (x) * 1ll * (x)
  14. #define all(x) x.begin(), x.end()
  15.  
  16. const int inf = 1e9;
  17. const int mod = 1e9 + 7;
  18. const double eps = 1e-6;
  19.  
  20.  
  21. string s;
  22. int p[10100];
  23.  
  24. int main(){
  25. ios_base::sync_with_stdio(0), cin.tie(0);
  26.  
  27. cin>>s;
  28.  
  29. string rs = "";
  30.  
  31. int n = sz(s);
  32.  
  33. for(int i=0; i<n; i++)
  34. rs[n-1-i] = s[i];
  35.  
  36.  
  37. p[0] = 0;
  38. int k = 0;
  39.  
  40. for(int i = 1; i<n; i++){
  41. while(k>0 && rs[k] != rs[i])
  42. k = p[k-1];
  43. if(rs[i] == rs[k]) k++;
  44. p[i] = k;
  45.  
  46. }
  47.  
  48. k = 0;
  49.  
  50. for(int i = 0; i<n; i++){
  51. while(k>0 && s[i] != s[k]){
  52. k = p[k-1]; }
  53. if(s[i] == s[k])
  54. k++;
  55. if(k == n)
  56. k = p[k-1];
  57. }
  58.  
  59. cout<<s;
  60.  
  61. for(int i=k+1; i<n; i++)
  62. cout<<rs[i];
  63.  
  64.  
  65. return 0;
  66.  
  67.  
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement