[Jsoi2013]快乐的jyy

题目

这个需要我们瞎\(yy\)一下就能做了

我们先对于第一个串建立\(PAM\)

我们把第二个串丢上去匹配，这里匹配出来的是以每一个位置为结尾且在另一个串里存在的最长回文后缀的长度

对于每一个位置开一个计数器，统计一下这个位置被匹配到了几次

显然匹配完之后把计数器做一个子树和

最后的答案就是回文树上的每一个位置代表的回文串出现的次数乘以当前位置计数器的值，之后求一个和

记得用回文树匹配的时候需要判断到了\(1\)位置时退出

代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read() {

	char c=getchar();int x=0;while(c<'0'||x>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int maxn=55555;

int son[maxn][26],fa[maxn],len[maxn],sum[maxn],val[maxn];

char S[maxn],T[maxn];

int n,m,cnt,lst;LL ans;

inline void ins(int c,int n) {

	int f=lst;

	while(S[n-len[f]-1]!=S[n]) f=fa[f];

	if(!son[f][c]) {

		int p=++cnt,k=fa[f];len[p]=len[f]+2;

		while(S[n-len[k]-1]!=S[n]) k=fa[k];

		fa[p]=son[k][c],son[f][c]=p;

	}

	++sum[lst=son[f][c]];

}

inline void find(int c,int n) {

	int f=lst;

	while(f!=1&&(T[n-len[f]-1]!=T[n]||!son[f][c])) f=fa[f];

	if(T[n-len[f]-1]==T[n]&&son[f][c]) ++val[lst=son[f][c]];

		else lst=1;

}

int main() {

	scanf("%s",S+1);scanf("%s",T+1);

	n=strlen(S+1),m=strlen(T+1);

	S[0]=-1;T[0]=-1;len[1]=-1,fa[0]=1;cnt=1;

	for(re int i=1;i<=n;i++) S[i]-='A';

	for(re int i=1;i<=m;i++) T[i]-='A';

	for(re int i=1;i<=n;i++) ins(S[i],i);

	for(re int i=cnt;i;--i) sum[fa[i]]+=sum[i];lst=0;

	for(re int i=1;i<=m;i++) find(T[i],i);

	for(re int i=cnt;i;--i) val[fa[i]]+=val[i];

	for(re int i=2;i<=cnt;i++) ans+=1ll*sum[i]*val[i];

	printf("%lld\n",ans);

	return 0;

}

秒客网

[Jsoi2013]快乐的jyy

相关文章