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 <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[2000001];
int main() {
    int N;
    scanf("%d", &N);
    while(N--) {
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        string t, str("\n");
        cin >> t;
        int sz = t.size(), mx = 0;
        for(int i = 0; i < sz; ++i) {
            str += t[i];
            str += '\n';
        }
        sz = str.size();
        for(int i = 1; i < sz; ++i) {
            if(mx + dp[mx] > i) {
                int j = (mx << 1) - i;
                dp[i] = min(dp[j], mx + dp[mx] - i);
            }
            while(i - dp[i] >= 0 && i + dp[i] < sz && str[i - dp[i]] == str[i + dp[i]])
                ++dp[i];
            mx = i + dp[i] > mx + dp[mx] ? i : mx;
        }
        int index = 0;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX