POJ3415 Common Substrings 【后缀数组 + 单调栈】-白红宇

POJ3415 Common Substrings 【后缀数组 + 单调栈】

阅读量：5275 次

发布时间：2019-06-14

本文共 3477 字，大约阅读时间需要 11 分钟。

常见的子串

时间限制： 5000MS		内存限制： 65536K
提交总数： 11942		接受： 4051

描述

字符串T的子字符串被定义为：

（

我

，

）=

Ť _我 Ť _我

₁

...

Ť _{I + K}

_-1

，1≤

我

≤

I + K

-1≤|

|。

给定两个字符串A，B和一个整数K，我们定义S，一组三元组（i，j，k）：

= {（

，

）|

≥

，

甲

（

我

，

）=

乙

（

，

）}。

你要给的价值| S | 特定甲，乙和ķ。

输入

输入文件包含几个数据块。对于每个块，第一行包含一个整数ķ，随后包含字符串两行阿和乙分别。输入文件以K = 0 结尾。

1≤| A |，| B | ≤10 ⁵

1≤ ķ ≤ 分钟 {| A |，| B |} A和B的

字符都是拉丁字母。

产量

对于每种情况，输出一个整数| S |。

示例输入

2aababaaabaabaa1XXXX0

示例输出

22五

蜜汁翻译。。额不要在意

挺难的一题，弱弱的我码了一个中午

首先后缀数组双串匹配，同样的操作，两串链接用一字符隔开，跑一遍sa

重点就是如何求出公共前缀大于等于K的子串数

首先如果lcp(i,j) = len 【len >ｋ】那么len - 1也满足

所以对于lcp(i,j)，它的贡献是len - k + 1

我们利用height数组分组，每一个组内的AB串都可以匹配，统计答案即可

但这样会T，因为这样做其实是O(n^2)的

怎么办呢？

我们需要维护一个单调栈，扫两次

第一次：对于每个A，统计它前面的B对于答案的贡献

我们知道两串在height数组之间的最小值即为其最长公共前缀长度，

对于A前第一个B之后的一个最小值，一定会影响到之前左右的B，但是B与B之间的最小值只会影响到前面的B而不影响到后面的B

因此我们维护一个单调递增单调栈，如果当前height比栈顶小，那么栈顶所对应的那些后缀会受到此height的影响【因为之前的B到后面的A一定会跨过这个地方，而这个地方height较小】，就合并栈顶【注意是合并】

看代码吧

#include
    
     #include
     
      #include
      
       #include
       #include
        
         #define LL long long int#define REP(i,n) for (int i = 1; i <= (n); i++)#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)using namespace std;const int maxn = 200005,maxm = 100005,INF = 1000000000;inline int RD(){	int out = 0,flag = 1; char c = getchar();	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}	while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}	return out * flag;}char s[maxn],B[maxn];int sa[maxn],rank[maxn],height[maxn],t1[maxn],t2[maxn],c[maxn],n,m,K,lA;void SA(){	int *x = t1,*y = t2;	for (int i = 0; i <= m; i++) c[i] = 0;	for (int i = 1; i <= n; i++) c[x[i] = s[i]]++;	for (int i = 1; i <= m; i++) c[i] += c[i - 1];	for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i;	for (int k = 1; k <= n; k <<= 1){		int p = 0;		for (int i = n - k + 1; i <= n; i++) y[++p] = i;		for (int i = 1; i <= n; i++) if (sa[i] - k > 0) y[++p] = sa[i] - k;		for (int i = 0; i <= m; i++) c[i] = 0;		for (int i = 1; i <= n; i++) c[x[y[i]]]++;		for (int i = 1; i <= m; i++) c[i] += c[i - 1];		for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];		swap(x,y);		p = 1; x[sa[1]] = 1;		for (int i = 2; i <= n; i++)			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p;		if (p >= n) break;		m = p;	}	REP(i,n) rank[sa[i]] = i;	int k = 0;	REP(i,n){		if (k) k--;		int j = sa[rank[i] - 1];		while (s[i + k] == s[j + k]) k++;		height[rank[i]] = k;	}}pair
         
           st[maxn];int top;LL ans;void solve(){ LL sum = 0; top = 0; for (int i = 2; i <= n; i++){ if (height[i] < K){ top = 0; sum = 0; }else { int num = 0; if (sa[i - 1] > lA + 1) num++,sum += height[i] - K + 1; while (top && height[i] <= st[top].first){ sum -= st[top].second * (st[top].first - height[i]); num += st[top--].second; } st[++top] = make_pair(height[i],num); if (sa[i] <= lA) ans += sum; } } top = 0; sum = 0; for (int i = 2; i <= n; i++){ if (height[i] < K){ top = 0; sum = 0; }else { int num = 0; if (sa[i - 1] <= lA) num++,sum += height[i] - K + 1; while (top && height[i] <= st[top].first){ sum -= st[top].second * (st[top].first - height[i]); num += st[top--].second; } st[++top] = make_pair(height[i],num); if (sa[i] > lA + 1) ans += sum; } }}int main(){ while (K = RD()){ scanf("%s",s + 1); lA = strlen(s + 1); strcat(s + 1,"#"); scanf("%s",B + 1); strcat(s + 1,B + 1); ans = 0; m = 256; n = strlen(s + 1); SA(); solve(); printf("%lld\n",ans); } return 0;}