[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