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

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

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; }




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