POJ 3415 Common Substrings (后缀数组,单调栈优化)

给出两个串,定义f(i, j, k)表示A[i…..i + k – 1] = B[j…..j + k – 1],这样(i, j, k)的对数有多少,k满足 >= K(给定的数)

首先明确一点对于任意两个前缀A[i]和B[j],假设他们的lcp = L, 那么他们对整体的贡献是L – k + 1,但是直接枚举i,j必定会超时。

可以根据K分组, 对于每组的答案是相符独立的。

现在单独考虑一组,问题变成:

1.求A后缀前面的B后缀和他lcp – k + 1的和

2.求B后缀前面的A后缀和他lcp – k + 1的和

因为任意两个后缀的lcp必定是这段区间height的最小值,所以可以维护一个单调栈,不断更新当前后缀和前面后缀lcp的和。

 

LEAVE A COMMENT