Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const char DUMMY = '#';
- int manacher(string s) {
- int n = s.size() * 2 - 1;
- vector <int> f = vector <int>(n, 0);
- string a = string(n, DUMMY);
- for (int i = 0; i < n; i += 2) a[i] = s[i / 2];
- int l = 0, r = -1, cen, res = 0;
- for (int i = 0, j = 0; i < n; i++) {
- j = (i > r ? 0 : min(f[l + r - i], r - i)) + 1;
- while (i - j >= 0 && i + j < n && a[i - j] == a[i + j]) j++;
- f[i] = --j;
- if (i + j > r) {
- r = i + j;
- l = i - j;
- }
- int len = (f[i] + i % 2) / 2 * 2 + 1 - i % 2;
- if (len > res) {
- res = len;
- cen = i;
- }
- }
- //in ra xau con dai nhat
- //cout << cen << "\n" << res << "\n";
- //if(cen % 2 == 0) cout << s.substr( cen / 2 - res/2, res) << "\n";
- //else cout << s.substr( (cen+1)/2 - res/2, res);
- return res;
- }
- signed main(){
- int c; cin >> c;
- string s; cin >> s;
- court << manacher(s);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement