Leave a Comment
本来想用后缀数组乱搞下，结果TL，于是怒上manacher, AC
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1100000 << 1; int s[maxn], p[maxn]; char str[maxn]; int manacher(int n){ int len = 0, ans = 0; s[len++] = -2; s[len++] = -1; for (int i = 0; i < n; i++){ s[len++] = str[i] - 'a' + 1; s[len++] = -1; } int mx = 0, id; for (int i = 0; i < len; i++){ if (mx > i) p[i] = min(p[2 * id - i], mx - i); else p[i] = 1; while (s[i - p[i]] == s[i + p[i]]) p[i]++; if (i + p[i] > mx){ mx = i + p[i]; id = i; } ans = max(ans, p[i] - 1); } return ans; } int main(){ int T; scanf("%d", &T); while(T--){ scanf("%s", str); int len = strlen(str); printf("%d\n", manacher(len)); } return 0; } |