Description
A substring of a string T is defined as:
T( i, k)= TiTi+1... Ti+k-1, 1≤ i≤ i+k-1≤| T|.
Given two strings A, B and one integer K, we define S, a set of triples (i, j, k):
S = {( i, j, k) | k≥ K, A( i, k)= B( j, k)}.
You are to give the value of |S| for specific A, B 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;
}