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
#include <iostream>
#include <string>
using namespace std;
string preProcess(string s)
{
    int len = s.length();
    if (len == 0)
        return "$";
    string ans = "$";
    for (int i = 0; i < len; i++)
        ans += "#" + s.substr(i, 1);
    return ans + "#";
}
int solve(string s)
{
    string T = preProcess(s);
    int len = T.length();
    int *p = new int[len];
    int mx = 0, id = 0;
    for (int i = 1; i < len; i++)
    {
        p[i] = mx > i ? min(p[2*id-i], mx - i) : 1;
        while (T[i+p[i]] == T[i-p[i]])
            p[i]++;
        if (i + p[i] > mx) 
        {
            mx = i + p[i];
            id = i;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX