#include<bits/stdc++.h>
#include<cmath>

#define mem(a,b) memset(a,b,sizeof a)
#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn=100100;
char a[maxn*2]; // $ # s[]
int b[maxn*2]; // RL[]

// 时间复杂度 O(n)
int manacher(char s[])
{
    int rs=-1;
    int len=strlen(s);
    int k=0;
    a[k++]='$';
    a[k++]='#';
    for(int i=0;i<len;i++)
        a[k++]=s[i],a[k++]='#';
    a[k]=0; // '\0'
    // 以上预处理，如：abba ---> $#a#b#b#a#'\0' （从0开始）

    // 表示当前访问到的所有回文子串，所能触及的最右一个字符的位置+1（即：最右边一个回文字符串的下一个位置）
    // mxr 对应的回文串的对称轴所在的位置，记为pos
    int mxr=0,pos=0;
    for(int i=0;i<k;i++)
    {
        /*

         从左往右地访问字符串来求RL[]（b[]），假设当前访问到的位置为i，即要求RL[i]，i必然是在po右边的
         但我们更关注的是，i是在MaxRight（mxr）的左边还是右边。我们分情况来讨论：
         1、当i在MaxRight的左边：
              以pos为对称轴，记右边边界为mxr，左边边界为mxl，(mxl,mxr)区间（注意：不包括mxl、mxr）的串是回文的；
              并且以当前 i 为对称轴的回文串，是与(mxl,mxr)区间的回文串有所重叠的。
              找到i关于pos的对称位置j，这个j对应的RL[j]前面是已经算过的。
              根据回文串的对称性，以i为对称轴的回文串和以j为对称轴的回文串，有一部分是相同的。
              这里又有两种细分的情况：
                  (1)、以j为对称轴的回文串比较短，短到没有超过边界mxl：
                          这时我们知道RL[i]至少不会小于RL[j]，并且已经知道了部分的以i为中心的回文串，于是可以令RL[i]=RL[j]。
                          但是以i为对称轴的回文串可能实际上更长，因此我们试着以i为对称轴，继续往左右两边扩展，直到左右两边字符不同，或者到达边界。
                  (2)、以j为对称轴的回文串很长，长到超过了边界mxl：
                          这时，我们只能确定，以i为对称轴，半径小于mxr的部分是回文的，于是从这个长度开始，尝试以i为中心向左右两边扩展，直到左右两边字符不同，或者到达边界。

         2、当i在MaxRight的右边或者重合（i==mxr）：
              遇到这种情况，说明以i为对称轴的回文串还没有任何一个部分被访问过，于是只能从i的左右两边开始尝试扩展了，当左右两边字符不同，或者到达字符串边界时停止。然后更新MaxRight和pos。

         参数说明：
              b[2*pos-i]：1-(1)，补充数学公式：(i+j)/2==pos
                   mxr-i：1-(2)
                       1：2
        */
        b[i]=mxr>i?min(b[2*pos-i],mxr-i):1;

        while(a[i+b[i]]==a[i-b[i]]) // 无需处理边界问题，因为我们一开始预处理 $、'\0'
            b[i]++;

        if(i+b[i]>mxr) // 不论以上哪种情况，之后都要尝试更新 mxr 和 pos，因为有可能得到更大的 mxr。
            mxr=i+b[i],pos=i;

        rs=max(rs,b[i]-1); // 更新最长回文串的长度
    }

    return rs;
}

int main()
{
    char s[maxn];
    while(gets(s))
    {
        printf("%d\n",manacher(s));
    }

    return 0;
}
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.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.

#include<bits/stdc++.h>
#include<cmath>

#define mem(a,b) memset(a,b,sizeof a)
#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn=100100;
char a[maxn*2];
int b[maxn*2];

int manacher(char s[])
{
    int rs=-1;
    int len=strlen(s);
    int k=0;
    a[k++]='$';
    a[k++]='#';
    for(int i=0;i<len;i++)
        a[k++]=s[i],a[k++]='#';
    a[k]=0;
    int mxr=0,pos=0;
    for(int i=0;i<k;i++)
    {
        b[i]=mxr>i?min(b[2*pos-i],mxr-i):1;

        while(a[i+b[i]]==a[i-b[i]])
            b[i]++;

        if(i+b[i]>mxr)
            mxr=i+b[i],pos=i;

        rs=max(rs,b[i]-1);
    }

    return rs;
}

int main()
{
    char s[maxn];
    while(gets(s))
    {
        printf("%d\n",manacher(s));
    }

    return 0;
}
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.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.