Advertisement
Guest User

Untitled

a guest
Jan 21st, 2018
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fi first
  6. #define se second
  7. #define pf push_front
  8. #define pb push_back
  9. #define mk make_pair
  10. #define all(c) (c).begin(), (c).end()
  11. #define sz(x) (int)x.size()
  12. #define SWS ios_base::sync_with_stdio(false)
  13. #define rfile freopen("input.txt", "r", stdin)
  14. #define wfile freopen("output.txt", "w", stdout)
  15. #define files rfile; wfile
  16.  
  17. typedef long long ll;
  18. typedef long double ld;
  19.  
  20. const int Z = (int)1e5 + 111;
  21. const int inf = (int)1e9 + 111;
  22. const ll llinf = (ll)1e18 + 5;
  23. const int MOD = (int)1e9 + 7;
  24.  
  25. vector<int> dd1 (string s) {
  26. int n = sz(s);
  27. vector<int> d1 (n);
  28. int l=0, r=-1;
  29. for (int i=0; i<n; ++i) {
  30. int k = (i>r ? 0 : min (d1[l+r-i], r-i)) + 1;
  31. while (i+k < n && i-k >= 0 && s[i+k] == s[i-k]) ++k;
  32. d1[i] = k--;
  33. if (i+k > r)
  34. l = i-k, r = i+k;
  35. }
  36. return d1;
  37. }
  38.  
  39. vector <int> dd2 (string s) {
  40. int n = sz(s);
  41. vector<int> d2 (n);
  42. int l=0, r=-1;
  43. for (int i=0; i<n; ++i) {
  44. int k = (i>r ? 0 : min (d2[l+r-i+1], r-i+1)) + 1;
  45. while (i+k-1 < n && i-k >= 0 && s[i+k-1] == s[i-k]) ++k;
  46. d2[i] = --k;
  47. if (i+k-1 > r)
  48. l = i-k, r = i+k-1;
  49. }
  50. return d2;
  51. }
  52.  
  53. int main () {
  54. srand(time(0));
  55. //files;
  56. string s, t;
  57. cin >> s;
  58. t = s;
  59. //reverse(all(t));
  60. s.pop_back();
  61. s = t + s;
  62. //cout << s << '\n';
  63. vector <int> ans;
  64. vector <int> d1 = dd1(s), d2 = dd2(s);
  65.  
  66. for (int i = 0; i < d1.size(); i++) {
  67. ans.pb(d1[i] * 2 - 1);
  68. ans.pb(d2[i] * 2);
  69. }
  70. int aans = 0;
  71. for (int i = 0; i < ans.size(); i++)
  72. if (ans[i] <= t.length()) {
  73. aans = max(aans, ans[i]);
  74. }
  75. cout << aans;
  76.  
  77. return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement