1
2
3
4
5
6
7
8
9
10
11

for(int i = 0, l = 0, r = -1;i<s2.size(); i++){
    int k = (i>r)? 1 : min(p[l+r-i], r-i+1);
    while(0 <= i-k && i+k<s2.size() && s2[i-k]==s2[i+k]){
        k++;
    }
    p[i] = --k; 
    if(i+k>r){
        l = i-k;
        r = i+k;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(設 x 表示 [l,r] 對稱中心，j 就是 i 關於 x 的對稱點)

1. 案例1
l       r
#a#b#b#a#
  ^ ^ ^
  j x i

2. 案例2
l     r
#a#b#a#b#a#b#a#
   ^   ^   ^
   j   x   i

手推方便理解

1

int k = (i>r)? 1 : min(p[l+r-i], r-i+1);

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

#include <cstdio>
#include <iostream>
#include <string>

using namespace std;

int p[110000001];

int main() {
    
    string s1;
    cin >> s1;
    string s2;
    s2.resize(s1.size()*2+4);
    s2[0] = '~';
    s2[1] = '#';
    for(int i = 0, j=2; i<s1.size(); i++, j+=2){
        s2[j] = s1[i];
        s2[j+1] = '#';
    }
    int ans = 0;
    for(int i = 0, l = 0, r = -1;i<s2.size(); i++){
        int k = (i>r)? 1 : min(p[l+r-i], r-i+1);
        while(0 <= i-k && i+k<s2.size() && s2[i-k]==s2[i+k]){
            k++;
        }
        k--;
        p[i] = k;
        if(i+k>r){
            l = i-k;
            r = i+k;
        }
        ans = max(ans,p[i]);
    }
    cout << ans << endl;
    return 0;
}