Description

---

给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.

字符串长度为n

Input

---

一行小写英文字符a,b,c…y,z组成的字符串S

Output

---

一个整数表示答案

Data Constraint

---

字符串长度len <= 11000000

Solution

---

manacher裸题，纯粹找手感

Code

---

#include <stdio.h> #include <string.h> #define rep(i, st, ed) for (int i = st; i <= ed; i += 1) #define min(x, y) (x)<(y)?(x):(y) #define max(x, y) (x)>(y)?(x):(y) #define L 22000003 int rad[L]; char rd[L], str[L]; int main(void){ scanf("%s", rd); int len = strlen(rd); str[0] = '#'; rep(i, 0, len - 1){ str[i * 2 + 1] = rd[i]; str[i * 2 + 2] = '#'; } len = len * 2 + 1; int pos = 0, mx = 0; int ans = 0; rep(i, 0, len){ rad[i] = 0; if (i < mx){ rad[i] = min(rad[pos - (i - pos)], mx - i); } while (i + rad[i] + 1 < len && i - rad[i] > && str[i + rad[i] + 1] == str[i - rad[i] - 1]){ rad[i] += 1; } if (rad[i] + i > mx){ mx = rad[i] + i; pos = i; } ans = max(ans, rad[i]); } printf("%d\n", ans); return 0; }