题目地址:https://www.lydsy.com/JudgeOnline/problem.php?id=4480
题目:
Description
【故事背景】
JYY在JSOI有很多很多的好朋友,比如PUPPY,KFC还有PUPPUP。因为
有了这么多的好朋友,所以JYY每天都很快乐。某天,JYY发现好朋友之间关
系的好坏和名字有很大的关系,比如PUPPY和PUPPUP的关系就特别好,但是
和KFC的关系就很一般。JYY苦思冥想终于发现了其中的规律,现在JYY想知
道两个朋友之间关系的好坏,你能帮助JYY么?
【问题描述】
给定两个字符串A和B,表示JYY的两个朋友的名字。我们用A(i,j)表示A
字符串中从第i个字母到第j个字母所组成的子串。同样的,我们也可以定义B(x,y)。
JYY发现两个朋友关系的紧密程度,等于同时满足如下条件的四元组(i,j,x,y)
的个数:
1:1<=i<=j<=|A|
2:1<=x<=y<=|B|
3:A(i,j)=B(x,y)
4:A(i,j)是回文串
这里表示字符串A的长度。
JYY希望你帮助他计算出这两个朋友之间关系的紧密程度。
Input
数据包行两行由大写字母组成的字符串A和B
1≤|A|,|B|≤50000。
Output
包含一行一个整数,表示紧密程度,也就是满足要求的4元组个数
Sample Input
PUPPY
PUPPUP
Sample Output
17
解题思路:
对第一个字符串构造回文树,将last和n重置为0,在当前回文树的基础上不添加重复节点的继续构造回文树,相当于两棵回文树的合并,并统计两个字符串中每个节点的cnt[]值,最终结果: ,其中p是最后一个节点的编号(程序中应该是p-1)
以样例为例,建立的回文树如下:
黑线表示在当前回文串两侧加新的字符形成新的回文串,如0->a->b表示在?️的两侧加a形成aa,在aa的两侧加b形成baab
红线表示第一个字符串的fail指针
蓝线表示第二个字符串新产生的fail指针
ac代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50005;
typedef long long ll;
int fail[maxn], cnt1[maxn], cnt2[maxn], len[maxn], nxt[maxn][26], s1[maxn], s2[maxn];
int last, n, p, ln;
char ss[maxn];
int newnode(int l,int cnt[]) //l是节点对应的最长回文子串的长度
{
for(int i = 0; i < 26; i++)
nxt[p][i] = 0;
len[p] = l;
cnt[p] = 0;
return p++;
}
void init()
{
p = 0, last = 0, n = 0, s1[0] = -1, s2[0] = -1;
newnode(0,cnt1); // p=0的初始化
newnode(-1,cnt1); // p = 1的初始化,之后 p = 2
fail[0] = 1;
fail[1] = 0;
}
int get_fail(int x,int s[])
{
while(s[n - len[x] - 1] != s[n])
x = fail[x];
return x;
}
void insert(int c, int s[],int cnt[]) // c = ch - 'a'
{
s[++n] = c;
int cur = get_fail(last,s);
if(!nxt[cur][c])
{
int now = newnode(len[cur] + 2,cnt); //now表示当前节点编号
fail[now] = nxt[get_fail(fail[cur], s)][c];
nxt[cur][c] = now;
}
last = nxt[cur][c];//当前节点编号
cnt[last]++;//以last为结尾的最长回文子串对应的数目+1
}
void count()
{
for(int i = p - 1; i >= 2; i--) //从后往前更新
{
cnt1[fail[i]] += cnt1[i];
cnt2[fail[i]] += cnt2[i];
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
init();
scanf("%s", ss+1);
ln = strlen(ss+1);
for(int i = 1; i <= ln; i++)
insert(ss[i] - 'A', s1, cnt1);
scanf("%s", ss+1);
last = 0, n = 0;
ln = strlen(ss+1);
for(int i = 1; i <= ln; i++)
insert(ss[i] - 'A', s2, cnt2);
count();
ll ans = 0;
for(int i = 2; i < p; i++)
ans += (1LL * cnt1[i] * cnt2[i]);
printf("%lld\n", ans);
return 0;
}