luogu P3649 [APIO2014]回文串

本文主要是介绍luogu P3649 [APIO2014]回文串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面传送门
结合manacher的拓展过程以及复杂度证明可以知道，一个序列的本质不同回文串是\(O(n)\)个，并且每次拓展时会出现一个可能本质不同的字符串。
那么就把这个回文串扔到SAM上查出现次数就好了。时间复杂度\(O(n\log n)\)
如果这样那也就不会有这篇题解了。
但是问题在于空间开不下。主要空间有\(O(n|\sum|)\)的SAM和\(O(n\log n)\)的倍增。
我先把SAM换成map，因为据说SAM的转移数是不超过\(3n-2\)的，但是好像map的空间不咋地，常数很大。
然后我又把倍增砍了一半，即大于\(2^9\)的暴力跳，小于\(2^9\)的再倍增，这样空间砍了一半，时间差不多是\(O(n\sqrt n)\)的。就可以过了。
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N (600000+5)
#define M (100+5)
#define K (200000+5)
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;
int n,m,k,H,lg[N],Id[N],ToT,Mid,Len,F[N];ll Ans;char A[N],S[N];
namespace SAM{
	int La=1,p,q,cnt=1,Le[N],son[N][26],Fi[N],fa[N][10],d[N],Si[N];vector<int> S[N];I void Ins(int x){
		p=La;Le[La=++cnt]=Le[p]+1;Si[La]=1;while(p&&!son[p][x]) son[p][x]=La,p=Fi[p];if(!p) {Fi[La]=1;return;}q=son[p][x];if(Le[q]==Le[p]+1){Fi[La]=q;return;}
		Le[++cnt]=Le[p]+1;Mc(son[cnt],son[q]);Fi[cnt]=Fi[q];Fi[La]=Fi[q]=cnt;while(p&&son[p][x]==q) son[p][x]=cnt,p=Fi[p];
	}
	I void dfs(int x,int La){d[x]=d[La]+1;fa[x][0]=La;for(RI i=1;fa[x][i-1]&&i<10;i++) fa[x][i]=fa[fa[x][i-1]][i-1];for(RI i:S[x]) dfs(i,x),Si[x]+=Si[i];}
	I void BD(){for(RI i=2;i<=cnt;i++) S[Fi[i]].PB(i);dfs(1,0);}
	I int Jp(int x,int Len){while(Le[fa[x][9]]>=Len) x=fa[x][9];for(RI i=lg[d[x]];~i;i--) fa[x][i]&&Le[fa[x][i]]>=Len&&(x=fa[x][i]);return Si[x];}
}
int main(){
	freopen("1.in","r",stdin);
	RI i;scanf("%s",A+1);n=strlen(A+1);S[H=1]='$';S[H=2]='#';for(i=1;i<=n;i++) S[++H]=A[i],S[++H]='#',SAM::Ins(A[i]-'a'),Id[i]=SAM::La;S[++H]='&';
	for(i=2;i<=n*2;i++) lg[i]=lg[i/2]+1;Mid=1;SAM::BD();for(i=2;i<=H;i++){
		Mid+Len>=i&&(F[i]=min(F[2*Mid-i],Mid+Len-i));while(S[i+F[i]]==S[i-F[i]]) S[i-F[i]]^'#'&&(ToT=SAM::Jp(Id[(i+F[i]-1)/2],F[i]+1),Ans=max(Ans,1ll*ToT*(F[i]+1))),F[i]++;
		i+F[i]>Mid+Len&&(Mid=i,Len=F[i]);
	}printf("%lld\n",Ans);
}

这篇关于luogu P3649 [APIO2014]回文串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！