【HAOI2016】找相同字符


题意

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

分析

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

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

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

 

You may also like

LEAVE A COMMENT

Statistics

  • 1
  • 2,003

Categories

Archive