Description：

给两个串，求把第二个串在第一个串上暴力匹配的比较次数。

$1\leqslant n\leqslant 10^5$

Solution：

首先可以用 $KMP$ 求出匹配位置，然后就知道了失配的范围，比较次数不好直接计算，我们可以计算第二个串每一个前缀的贡献，也就是第二个串每一个前缀在第一个串上的出现次数，这个可以用线段树合并维护 $right$ 集合来统计，但是这样显然会算重，因为实际的匹配不一定到这里就截止了，因此和后一项做差才是实际到这里失配的比较次数，然后就可以统计答案了。

Code：

代码就不写了。