bzoj3676 回文串
程序员文章站
2022-06-17 11:26:07
题目链接 思路 看到回文串,自然就会想到 。 还要求子串长度。那就用$SAM$。 所以每次用manacher找到一个回文串,都在$SAM$上查询其出现次数。 在$SAM$上查询的时候,肯定不能暴力找。先找到当前回文串的结束位置。然后用倍增法往上跳。一直跳到长度和当前回文串长度相同。 这个题有点卡空间 ......
思路
看到回文串,自然就会想到。
还要求子串长度。那就用\(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; }