[POJ 3415 Common Substrings]后缀数组、分组思想、单调栈

【题目大意】

给定两个串,让你求满足A[i..i+k]=B[j..j+k]且k>=K的(i,j)的数目。

【算法分析】

先把两个串连在一起,中间加一个特殊字符。

然后建立后缀数组和height数组。

最后对height进行线性分组,同组的height都>=K

然后注意到我们需要统计的是每一个点对(i,j)其中i为A串的后缀,j为B串的后缀,他们的lcp(i,j)-limit+1,然后加起来。但是我们注意到越向后延伸,对于同一个点的lcp只会单调递减,然后用一个栈合并lcp已经被并为同一个数字的区间,最后输出就可以。

【其它】3WA,s1和s2忘记搞成long long了。。。

表示紧紧跟随lcc的脚步。。。

【CODE】

#include

加入对话

3条评论

留下评论

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