题目描述

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

解题报告

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

bzoj 4566

发表评论

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