UOJ#103. 【APIO2014】Palindromes PAM模板题

原文链接www.cnblogs.com/zhouzhendong/p/UOJ103.html

前言

  我终于会PAM啦

  感谢CLY大佬手把手教我PAM

题解

  建个 PAM。

  统计一下每一个节点的 Right 集合大小,设 size[x] 为节点 x 的 right 集合大小。

  求出 max(len[x] * size[x]) ,做完了。

代码

 #include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=a;i<=b;i++)
#define Fod(i,b,a) for (int i=b;i>=a;i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define _SEED_ ('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')
#define outval(x) printf(#x" = %d\n",x)
#define outvec(x) printf("vec "#x" = ");for (auto _v : x)printf("%d ",_v);puts("")
#define outtag(x) puts("----------"#x"----------")
#define outarr(a,L,R) printf(#a"[%d...%d] = ",L,R);\
For(_v2,L,R)printf("%d ",a[_v2]);puts("");
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> vi;
LL read(){
LL x=0,f=0;
char ch=getchar();
while (!isdigit(ch))
f|=ch=='-',ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
const int N=300005;
int n;
char s[N];
namespace PAM{
int len[N],Fail[N],Next[N][26];
int size[N];
int cnt;
void init(){
cnt=2;
len[1]=-1,Fail[1]=1;
len[2]=0,Fail[2]=1;
clr(Next),clr(size);
}
void build(char *s,int n){
init();
s[0]='*';
int x=1;
For(i,1,n){
while (s[i-len[x]-1]!=s[i])
x=Fail[x];
int c=s[i]-'a';
if (Next[x][c])
x=Next[x][c];
else {
int y=Next[x][c]=++cnt;
len[y]=len[x]+2;
if (len[y]==1)
Fail[y]=2;
else {
x=Fail[x];
while (s[i-len[x]-1]!=s[i])
x=Fail[x];
Fail[y]=Next[x][c];
}
x=y;
}
size[x]++;
}
Fod(i,cnt,1)
size[Fail[i]]+=size[i];
}
LL solve(){
LL ans=0;
For(i,2,cnt)
ans=max(ans,(LL)len[i]*size[i]);
return ans;
}
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
PAM::build(s,n);
cout<<PAM::solve()<<endl;
return 0;
}

  

上一篇:【读书笔记】iOS-Nib的一些知识


下一篇:CentOS下php使用127.0.0.1不能连接mysql的解决方法