首页 > 题解 > bzoj 4566 [Haoi2016]找相同字符

bzoj 4566 [Haoi2016]找相同字符

Description

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两
个子串中有一个位置不同。

Input

两行,两个字符串s1,s2,长度分别为n1,n2。1 <=n1, n2<= 200000,字符串中只有小写字母

Output

输出一个整数表示答案

Sample Input

aabb

bbaa

Sample Output

10

题解

对一个串A建自动机,另一个串B在上面匹配

考虑怎么统计答案

对于当前匹配到的点,那么它parent树中的祖先代表的串现在肯定也出现了

对于每个出现的点,它代表了maxs[x]-mins[x]+1个串(mins[x]=maxs[fa[x]]+1)

这些串出现了|right(x)|次,贡献就是|right(x)|*(maxs[x]-maxs[fa[x]])

因为要统计祖先的,所以把祖先的也累加到这个节点即可


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×