POJ – 3415 Common Substrings 后缀数组+单调栈+前缀和

Common Substrings 后缀数组+单调栈+前缀和

 Source

POJ - 3415

My Solution

题意：给出两个字符串，求出它们的相同的长度至少为k的子串的个数。

后缀数组+单调栈+前缀和

把a、b这两个字符串用'#'连起来，然后求出它们的后缀数组，然后后缀ai和后缀bi的的满足要求的子串的个数是 max(0, LCP(suffixai, suffixbj) - k + 1);

根据后缀数组的性质，也就是后缀i后缀j的LCP 等于这段height的最小值。

因此对于每个ai考虑ai之前的所有bi， sum{max(0, LCP(suffixai, suffixbj) - k + 1)} rank[ai] > rank[bi];

然后反向扫一遍，也就是对于每个bi考虑bi之前的所有aj， sum{max(0, LCP(suffixaj, suffixbi) - k + 1)} rank[bi] > rank[aj];

然后这个 sum{max(0, LCP(suffixai, suffixbj) - k + 1)} rank[ai] > rank[bi]; 可以用单调栈来维护。

但height[i] < k时把栈清空， 否则如果栈顶 height >= height[i]则 出栈，直到不满足时把height入栈。对于栈中的每个元素维护一个cnt，

表示从Ind[sta[x]]到Ind[sta[x+1]] - 1这height数组中的元素个数，且这段区间的最小值(>=k)是sta[x],个数是cnt[x]个，所以这个区间内的后缀和i的LCP都是sta[x],

所以这段区间对答案的贡献是 (sta[x] - x + 1)*cnt[x]，然后用前缀和来维护栈中元素的和，每次维护时 sum[top] = sum[top-1] + (sta[top] - k + 1)*cnt[top]即可。

然后sum[maxn] 和 ans 记得用long long即可

复杂度 O(nlogn)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 8;
int sa[maxn], height[maxn];
int _rank[maxn], t1[maxn], t2[maxn], c[maxn];
string s, s2;
inline void get_sa(const int &n, int m)
{
    memset(t2, -1, sizeof t2);
    int i, k, *x = t1, *y = t2, p, j;
    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(k = 1; k <= n; k <<= 1){
        p = 0;
        for(i = n - k; i < n; i++) y[p ++] = i;
        for(i = 0; i < n; i++) if(sa[i] >= k) y[p ++] = sa[i] - k;
        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]+k] == y[sa[i]+k]) ? p - 1 : p ++; if(p >= n) break;
        m = p;
    }
    k = 0;
    for(i = 0; i < n; i++) _rank[sa[i]] = i;
    for(i = 0; i < n; i++){
        if(k) --k; if(!_rank[i]) continue;
        j = sa[_rank[i] - 1];
        while(s[i + k] == s[j + k]) k++;
        height[_rank[i]] = k;
    }
}

inline void print(const int &n)
{
    for(int i = 0; i < n; i++){
        cout << height[i] << " ";
        for(int j = sa[i]; j < n; j++){
            cout << s[j];
        }
        cout << endl;
    }
    cout << endl; } LL sta[maxn], top, tmp, cnt[maxn]; //µ¥µ÷Õ» LL sum[maxn], ans; int main() { #ifdef LOCAL freopen("7.in", "r", stdin); //freopen("7.out", "w", stdout); #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int k, sz, i, sza, szb; while(true){ //cin >> m;
        cin >> k;
        if(k == 0) break;
        cin >> s >> s2; sza = s.size(), szb = s2.size();
        s += '#'; s += s2;
        sz = sza + szb + 1;
        get_sa(sz, 256);
        //print(sz);
        ans = top = 0;
        for(i = 1; i < sz; i++){
            if(height[i] < k) top = 0;
            else{
                tmp = sa[i-1] < sza; while(top && sta[top] >= height[i]){
                    tmp += cnt[top];
                    top--;
                }
                sta[++top] = height[i]; cnt[top] = tmp;
                sum[top] = sum[top - 1] + (sta[top] - k + 1) * cnt[top];
                if(sa[i] > sza) ans += sum[top];
            }
        } top = 0;
        for(i = 1; i < sz; i++){
            if(height[i] < k) top = 0; else{ tmp = sa[i-1] > sza;
                while(top && sta[top] >= height[i]){
                    tmp += cnt[top];
                    top--;
                }
                sta[++top] = height[i]; cnt[top] = tmp;
                sum[top] = sum[top - 1] + (sta[top] - k + 1) * cnt[top];
                if(sa[i] < sza) ans += sum[top];
            }
        }
        cout << ans << "n";

    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx