题目链接

思路

看到回文串，自然就会想到。

还要求子串长度。那就用(sam)。

所以每次用manacher找到一个回文串，都在(sam)上查询其出现次数。

在(sam)上查询的时候，肯定不能暴力找。先找到当前回文串的结束位置。然后用倍增法往上跳。一直跳到长度和当前回文串长度相同。

这个题有点卡空间。卡了很久才卡过去。

代码

/* * @author: wxyww * @date:   2019-07-12 17:23:51 * @last modified time: 2019-07-13 10:11:46 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int lgn = 20,n = 600000 + 100; // #define int ll ll read() {     ll x=0,f=1;char c=getchar();     while(c<'0'||c>'9') {         if(c=='-') f=-1;         c=getchar();     }     while(c>='0'&&c<='9') {         x=x*10+c-'0';         c=getchar();     }     return x*f; } char s[n],s[n]; struct node {     int fa,ch[26],len; }sam[n]; int siz[n],lst = 1,tot = 1,pos[n]; void add(int c,int id) {     int p = lst,cur = ++tot;     sam[cur].len = sam[lst].len + 1;     pos[id] = cur;siz[cur] = 1;     while(p && !sam[p].ch[c]) {         sam[p].ch[c] = cur;         p = sam[p].fa;     }     if(!p) sam[cur].fa = 1;     else {         int q = sam[p].ch[c];         if(sam[q].len == sam[p].len + 1) sam[cur].fa = q;         else {             int clone = ++tot;             sam[clone] = sam[q];             sam[clone].len = sam[p].len + 1;             while(p && sam[p].ch[c] == q) {                 sam[p].ch[c] = clone;                 p = sam[p].fa;             }             sam[cur].fa = sam[q].fa = clone;         }     }     lst = cur; } int p[n]; int n,tong[n],a[n],st[n][lgn + 1]; ll ans; void check(int l,int r) {     int p = pos[r];     for(int i = lgn;i >= 0;--i) {         if(sam[st[p][i]].len >= r - l + 1)              p = st[p][i];     }     ans = max(ans,1ll * (r - l + 1) * siz[p]); } void manacher() {     int id = 0,mx = 0;     for(int i = 1;i <= n;++i) {         if(id + mx > i) p[i] = min(id + mx - i,p[id * 2 - i]);          check((i - p[i] + 1) / 2,(i + p[i]) / 2);         while(i + p[i] + 1 <= n && i - p[i] - 1 >= 1 && s[i + p[i] + 1] == s[i - p[i] - 1]) {             p[i]++;              check((i - p[i] + 1) / 2,(i + p[i]) / 2);         }         if(i + p[i] > id + mx) id = i,mx = p[i];     } } int main() {     scanf("%s",s + 1);     int nn = strlen(s + 1);     s[++n] = '#';     for(int i = 1;i <= nn;++i) {         add(s[i] - 'a',i);         s[++n] = s[i];         s[++n] = '#';     }      for(int i = 1;i <= tot;++i) tong[sam[i].len]++;     for(int i = 1;i <= nn;++i) tong[i] += tong[i - 1];     for(int i = 1;i <= tot;++i) a[tong[sam[i].len]--] = i;     for(int i = tot;i >= 1;--i) siz[sam[a[i]].fa] += siz[a[i]];     siz[1] = 0;      for(int i = 1;i <= tot;++i) {         st[a[i]][0] = sam[a[i]].fa;         for(int j = 1;j <= lgn;++j) st[a[i]][j] = st[st[a[i]][j - 1]][j - 1];     }      manacher();     cout<<ans;     return 0; }