题意

求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。

分析

我们可以通过 endpos 的大小得到每一个状态出现的次数。

根据乘法原理,这道题目的答案就是两个 sam 中相同状态出现次数的乘积之和。

在图上按照转移边跑一遍就好了。

 


发表评论

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