代码暂存

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 3e5 + 5;
 4 #define ll long long
 5 struct Tree
 6 {
 7     int len,fail,go[26];//Go边指向添加字符后达到的状态，fail边指向当前状态字符串的最长回文后缀，类似于SAM
 8 }tr[maxn];
 9 char s[maxn];
10 int len,last,tot,nowi,cnt[maxn];//Cnt[i]表示状态i在母串中出现的次数
11 void init()
12 {
13     tr[0].len = 0,tr[1].len = -1;
14     tot = 1,last = 0;
15     tr[0].fail = 1;
16     nowi=0;
17 }
18 int get(int now)
19 {
20     while (s[nowi - tr[now].len - 1] != s[nowi]) now = tr[now].fail;
21     return now;
22 }
23 void add(int c)
24 {
25     nowi++;
26     int t = get(last);
27     if (!tr[t].go[c])
28     {
29         tr[++ tot].len = tr[t].len + 2;
30         tr[tot].fail = tr[get(tr[t].fail)].go[c];
31         tr[t].go[c] = tot;
32     }
33     last = tr[t].go[c];
34     cnt[last] ++;
35 }
36 ll getans()
37 {
38     ll ans = 0;
39     for (int i = tot; i > 1; i --)
40     {
41         cnt[tr[i].fail] += cnt[i];
42         ans = max(ans,1LL*tr[i].len*cnt[i]);
43     }
44     return ans;
45 }
46 int main()
47 {
48     scanf("%s",s + 1);
49     len = strlen(s + 1);
50     init();
51     for (int i = 1; i <= len; i ++) add(s[i] - ‘a‘);
52     printf("%lld",getans());
53 }