bzoj 4566 找相同字符

题目描述

bzoj 4566 题意:给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。|S|\leq 2\times 10^5

解题报告

首先可以意识到,我们可以把一个串建后缀自动机,然后另一个串在后缀自动机上跑,我们知道SAM建出的fail树的性质有:
(1):树上的一个节点代表了多个串,串的个数是l[x]-l[f[x]],同时他们都出现了sz[x]次。
(2):设串的长度为len,那么每个节点xsz[x](l[x]-l[f[x]])的和为\frac{len(len+1)}{2}
(3):树上一个节点的所有后代所代表的串都是以这个节点代表的串为后缀的串
(4):根据性质3推出: 如果一个字符串匹配到一个树上的某个节点, 那么这个节点的所有祖先所代表的所有祖先都是它的子串,但那个节点本身所代表的所以串并不一定都是他的子串。
我们假设处理到第i个字符的时候,把所有以s[i]结尾的子串都处理掉,那么假设当前匹配到 i 字符时转移到了节点x, 那么x对答案的贡献就是 祖先所代表的所有的串(可以预处理)和 匹配到 i 字符时,(第二个串与第一个串的最长匹配长度-l[f[x]])\times sz[x]
第二个串与第一个串的最长匹配长度-l[f[x]](这个就是第二个串在x节点内所能匹配的子串数)
写的时候又因为细节挂了,我好菜啊…

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注