POJ - 3415 Common Substrings(后缀数组求长度不小于 k 的公共子串的个数+单调栈优化)

时间:2024-11-13 22:06:20

Description

A substring of a string T is defined as:

Tik)= TiTi+1... Ti+k-1, 1≤ i≤ i+k-1≤| T|.

Given two strings AB and one integer K, we define S, a set of triples (ijk):

S = {( ijk) | k≥ KAik)= Bjk)}.

You are to give the value of |S| for specific AB and K.

Input

The input file contains several blocks of data. For each block, the first line contains one integer K, followed by two lines containing strings A and B, respectively. The input file is ended by K=0.

1 ≤ |A|, |B| ≤ 105

1 ≤ K ≤ min{|A|, |B|}

Characters of A and B are all Latin letters.

Output

For each case, output an integer |S|.

Sample Input

2
aababaa
abaabaa
1
xx
xx
0

题意:求长度不小于 k 的公共子串的个数。

思路:还是论文上的题目。基本思路是计算 A 的所有后缀和 B 的所有后缀之间的最长公共前缀的长度。把最长公共前缀长度不小于 k 的部分所有加起来。先将两个字符串连起来,中间用一个没有出现过的字符隔开。按 height 值分组后,接下来的工作便是高速的统计每组中后缀之间的最长公共前缀之和。扫描一遍,每遇到一个 B 的后缀就统计与前面的 A 的后缀能产生多少个长度不小于 k 的公共子串,这里 A 的后缀须要用一个单调的栈来高效的维护。然后对 A 也这样做一次。

比較难理解的是单调栈这部分。还是通过举例来说吧,如果当前的height[]数组按排名的顺序依次是:1,2,3.如果这些都大于等于k值,且sa[0],sa[1],sa[2]都是B串的,当sa[3]是A串的时候,由于它和sa[2]的最长公共前缀是3,所以能够包括住前3个B串,所以能够所有累加起来;可是如果是小于等于的话,比如是1的话,那么2和3的值就须要又一次计算了,由于此时的最长公共前缀是1了,我们还须要一个num[]数组来记录此时大于等于栈顶的值的个数,由于这在之后如果有更小的时候。还须要把这些大于等于的再减掉。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
const int maxn = 200010; int sa[maxn];
int t1[maxn], t2[maxn], c[maxn];
int rank[maxn], height[maxn]; void build_sa(int s[], int n, int m) {
int i, j, p, *x = t1, *y = t2;
for (i = 0; i < m; i++) c[i] = 0;
for (i = 0; i < n; i++) c[x[i] = s[i]]++;
for (i = 1; i < m; i++) c[i] += c[i-1];
for (i = n-1; i >= 0; i--) sa[--c[x[i]]] = i; for (j = 1; j <= n; j <<= 1) {
p = 0;
for (i = n-j; i < n; i++) y[p++] = i;
for (i = 0; i < n; i++)
if (sa[i] >= j)
y[p++] = sa[i] - j;
for (i = 0; i < m; i++) c[i] = 0;
for (i = 0; i < n; i++) c[x[y[i]]]++;
for (i = 1; i < m; i++) c[i] += c[i-1];
for (i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i]; swap(x, y);
p = 1, x[sa[0]] = 0;
for (i = 1; i < n; i++)
x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+j] == y[sa[i]+j] ? p-1 : p++; if (p >= n) break;
m = p;
}
} void getHeight(int s[],int n) {
int i, j, k = 0;
for (i = 0; i <= n; i++)
rank[sa[i]] = i; for (i = 0; i < n; i++) {
if (k) k--;
j = sa[rank[i]-1];
while (s[i+k] == s[j+k]) k++;
height[rank[i]] = k;
}
} int r[maxn];
int st[maxn], num[maxn];
char str1[maxn], str2[maxn];
int k, len1, len2; ll solve(int n, int k) {
ll i, j, tp, ans = 0;
ll tot, top;
for (i = 1; i <= n; i++) {
if (height[i] < k) tot = top = 0;
else {
tp = 0;
if (sa[i-1] > len1) {
tp = 1;
tot += height[i] - k + 1;
} while (top > 0 && st[top] >= height[i]) {
tot -= num[top] * (st[top] - height[i]);
tp += num[top];
top--;
} st[++top] = height[i];
num[top] = tp;
if (sa[i] < len1)
ans += tot;
}
} for (i = 1; i <= n; i++) {
if (height[i] < k) tot = top = 0;
else {
tp = 0;
if (sa[i-1] < len1) {
tp = 1;
tot += height[i] - k + 1;
} while (top > 0 && st[top] >= height[i]) {
tot -= num[top] * (st[top] - height[i]);
tp += num[top];
top--;
} st[++top] = height[i];
num[top] = tp;
if (sa[i] > len1)
ans += tot;
}
}
return ans;
} int main() {
int i, j;
while (scanf("%d", &k) != EOF && k) {
scanf("%s%s",str1,str2);
for (i = 0; str1[i]; ++i)
r[i] = str1[i];
r[i] = '$',len1 = i,i++;
for (j = 0; str2[j];j++)
r[i+j] = str2[j];
r[i+j] = 0;
int len = i + j; build_sa(r, len+1, 128);
getHeight(r, len); printf("%lld\n", solve(len, k));
}
return 0;
}