【链接】h在这里写链接
【题意】
求两个串的长度大于等于k的公共子串个数。
相同的重复计数。
【题解】
先把两个字符串用一个分隔符分开。最好比出现的字符都大的一个数字。
然后，对于这一个字符串，求出它的Height和Sa数组。
然后，把height 数组【连续】大于等于k的，分成一组去考虑。
(没有大于等于k了的话,显然子串的长度就不符合要求)
如果我们在【这一组】里遇到了一个a串的后缀。
那么显然，我们会在这个组里再找若干个b串的后缀。
然后分别求出这个a串和这些b串的最长公共前缀temp,然后累加temp-k+1就好.
但是这样实现的话,时间复杂度为O(n^2)
有一个性质,就是任意两个后缀的最长公共前缀为它们之间(排名之间)的height的最小值。
根据这个,用单调队列来做一个优化。
对于连续的大于等于k的height值。
i顺序扫过去。
遇到的如果是a串,那么直接cnt累加height[i]-k+1,然后把它放到单调队列里面
去,之后,如果再遇到a串的话,就看看是不是这个a串的height比之前的a串的height
值更小,如果更小的话,就用新的,更小的height去取代旧的且比较大的height;
(因为遇到了更小的,就说明,后面的b串如果要和a串递增答案,用的temp值就
更小了,则cnt也会相应改变)
这个过程就对应了,把单调队列的队尾的大的height给去掉。
然后更新cnt;(cnt是下次遇到b串的时候累加答案的)
然后把这个height[i]直接加到队列尾巴.
因为遇到了一个新的a的后缀,所以后面的b如果要和这个a后缀做答案,
肯定要从这个height[i]开始算最小值,后面如果有最小值,则后面再用
上面的方法改就好。
(之前虽然有更小的height,但是他们在[l,r]这个区间的左边。
因此把它加到队列是没有问题的.
如果遇到的是b串的后缀,那么,也应该用这个b串的后缀,来尝试改变一下单调
队列里面的最小值,如果可改的话,那么他就取代了某些a串的height值了。还
是一样,弹出队列尾巴比它大的。把这个新的加进去(因为是b的后缀,所以这个
加入到队列尾巴以后,除非他取代了之前的a串的height,否则不计算个数),然
后更改cnt的值。因为是b串,所以把之前的a串的cnt值累加进最后的答案就好。
(所以这个cnt值,就相当于是预先算出来了前面的所有a的后缀,和下一个会遇
到的b的后缀的答案的和)
然后要反过来做一遍。
即把b放在前面,遇到a累加b的答案。
比如
AABBAA
(A和B代表了A和B的一个后缀)
如果只做第一种
3->5
4->5
3->6
4->6
这4种就会漏掉
【错的次数】
【反思】
转化模型:
给你n个数字ai,
每个数字属于A或属于B;
对于所有属于B的数字a[i]
求出j<i;
且a[j]属于A,
temp = ∑(min(a[j..i])-k+1)
对于所有的a[i]的temp值求和
【代码】