- #include#include#include#include#include using namespace std;
- const int N = 1e5 + 5;
- int n;
- char s[N],
- str[N];
- void iniStr(char * str, char * s) {
- for (int i = 1; i <= n; i++) s[(i << 1) - 1] = '#',
- s[i << 1] = str[i];
- s[0] = '$';
- s[n << 1 | 1] = '#';
- }
- int r[N];
- void Manacher(char * s, int n) {
- int p = 0,
- a;
- for (int i = 1; i <= n; i++) {
- r[i] = i1,
- r[2 * a - i]) : 1;
- while (s[i - r[i]] == s[i + r[i]]) r[i]++;
- if (i + r[i] - 1 > p) p = i + r[i] - 1,
- a = i;
- }
- }
- struct Seq {
- int l,
- r;
- bool operator < (const Seq & a) const {
- return la.r);
- }
- }
- a[N];void solve() {
- n = n << 1;
- for (int i = 1; i <= n; i++) a[i].l = i - r[i] + 1,
- a[i].r = i + r[i] - 1;
- sort(a + 1, a + 1 + n);
- int now = a[1].r + 1,
- ans = 1,
- r,
- i = 2;
- while (now <= n) {
- r = 0;
- while (i <= n && a[i].l <= now) r = max(r, a[i].r),
- i++;
- now = r + 1;
- ans++;
- }
- printf("%d\n", ans - 1);
- }
- int main() {
- freopen("in", "r", stdin);
- while (scanf("%s", str + 1) != EOF) {
- memset(r, 0, sizeof(r));
- memset(s, 0, sizeof(s));
- n = strlen(str + 1);
- iniStr(str, s);
- Manacher(s, n << 1);
- solve();
- }
- }
来源: