POJ 3415 后缀数组

时间：2021-03-04 07:11:25

题目链接：http://poj.org/problem?id=3415

题意：给定2个串[A串和B串]，求两个串公共子串长度大于等于k的个数。

思路：首先是两个字符串的问题。所以想用一个'#'把两个字符串拼接起来。求后缀数组。 然后按照k把height数组分组。大于等于k的为一组，然后就是统计每组的贡献。对于每一组的贡献即是组内所有A串的后缀和B串的后缀的lcp值，即为val.那么val对于答案的贡献为(val-k+1)。如果我们暴力每组的AB串后缀的组合。时间复杂度是O(n^2).不能满足要求。所以要用另外的办法来优化计算。利用height数组的性质，满足单调不增的特点，所以我们可以用一个单调栈来优化计算。 对于每个分组。我们分2种情况来计算。一：把B串的后缀放入单调栈。每枚举到一个A串后缀就和单调栈的值进行计算贡献。二:把A串的后缀放入单调栈。每枚举到一个B串后缀就和单调栈的值进行计算贡献。 对于如何维护这个单调栈：如果对于情况一，如果每遇到一个A串后缀就和栈内所有的B后缀都计算一遍会退化到O(n^2).所以栈还要维护一个前缀贡献值，这样就可以把复杂度将为O(n)。       关于维护前缀贡献值是从这篇博客学习到的。 该题也可以用后缀自动机来写，而且好像比后缀数组容易。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<queue>

#include<vector>

#include<time.h>

#include<cmath>

#include<stack>

using namespace std;

typedef long long int LL;

const int MAXN =  *  + ;

int cmp(int *r, int a, int b, int l){

    return r[a] == r[b] && r[a + l] == r[b + l];

}

int wa[MAXN], wb[MAXN], wv[MAXN], WS[MAXN];

void da(int *r, int *sa, int n, int m){

    int i, j, p, *x = wa, *y = wb, *t;

    for (i = ; i < m; i++) { WS[i] = ; }

    for (i = ; i < n; i++) { WS[x[i] = r[i]]++; }

    for (i = ; i < m; i++) { WS[i] += WS[i - ]; }

    for (i = n - ; i >= ; i--) { sa[--WS[x[i]]] = i; }

    for (j = , p = ; p<n; j *= , m = p)

    {

        for (p = , i = n - j; i < n; i++) { y[p++] = i; }

        for (i = ; i < n; i++) {

            if (sa[i] >= j){ y[p++] = sa[i] - j; }

        }

        for (i = ; i < n; i++) { wv[i] = x[y[i]]; }

        for (i = ; i < m; i++) { WS[i] = ; }

        for (i = ; i < n; i++) { WS[wv[i]]++; }

        for (i = ; i < m; i++) { WS[i] += WS[i - ]; }

        for (i = n - ; i >= ; i--) { sa[--WS[wv[i]]] = y[i]; }

        for (t = x, x = y, y = t, p = , x[sa[]] = , i = ; i < n; i++){

            x[sa[i]] = cmp(y, sa[i - ], sa[i], j) ? p -  : p++;

        }

    }

    return;

}

int Rank[MAXN], height[MAXN], sa[MAXN];

void calheight(int *r, int *sa, int n){

    int i, j, k = ;

    for (i = ; i <= n; i++) { Rank[sa[i]] = i; }

    for (i = ; i < n; height[Rank[i++]] = k){

        for (k ? k-- : , j = sa[Rank[i] - ]; r[i + k] == r[j + k]; k++);

    }

    return;

}

int r[MAXN], len, k, index;

char str[MAXN];

struct Node{

    int cnt, height; LL sum;

    //cnt：后缀个数； height:sa[i]和sa[i-1]的lcp；sum:前缀贡献和

}S[MAXN];

void solve(){

    LL ans = ; int top=;

    for (int i = ; i <= len; i++){ //计算A串的贡献

        if (height[i] < k) top = ;

        else {

            int cnt = ;

            while (top && height[i] <= S[top - ].height) cnt += S[--top].cnt; //单调栈

            S[top].cnt = cnt + (sa[i - ] > index);  //属于B串

            S[top].height = height[i]; //记录height

            S[top].sum = top ? S[top - ].sum : ; //累加之前的[前缀]贡献

            S[top].sum += (LL)(S[top].height - k + ) * S[top].cnt; //计算当前贡献

            if (sa[i] < index) ans += S[top].sum; //属于A串，统计贡献

            top++;

        }

    }

    top = ;

    for (int i = ; i <= len; i++){ //与上面相反

        if (height[i] < k) top = ;

        else {

            int cnt = ;

            while (top && height[i] <= S[top - ].height) cnt += S[--top].cnt;

            S[top].cnt = cnt + (sa[i - ] < index);

            S[top].height = height[i];

            S[top].sum = top ? S[top - ].sum : ;

            S[top].sum += (LL)(S[top].height - k + ) * S[top].cnt;

            if (sa[i] > index) ans += S[top].sum;

            top++;

        }

    }

    printf("%lld\n", ans);

}

int main(){

    while (scanf("%d", &k) && k){

        scanf("%s", str); index = strlen(str); str[index] = '#';

        scanf("%s", str + index + ); len = strlen(str); str[len] = '$';

        for (int i = ; i <= len; i++){

            r[i] = str[i];

        }

        r[index] = ; r[len] = ;

        da(r, sa, len+, );

        calheight(r, sa, len);

        solve();

    }

    return ;

}

相关文章