洛谷P3181 后缀数组

迈不过友情╰ 2023-10-11 13:27 43阅读 0赞

> [https://www.luogu.org/problem/P3181][https_www.luogu.org_problem_P3181]

题目要求求出两个两个字符串中相同子串的方案数，那么我们将其拼接起来，去求出拼接后的字符串中含有相同子串的数量。

当然这样做会求出同一个字符串中相同子串的数量，所以我们还需要如法炮制分别求出两个字符串中的答案，然后用总贡献减去他们。

那么问题就变成了如何求出一个字符串中相同子串的数量。

实际上这就是求任意两个后缀x,y的lcp(x,y)和,利用后缀数组，可以知道任意两个lcp(x,y)为min\{Height\[i\]\} x <= i <= y

所以说问题在利用后缀数组求出Height数组之后转化为了如何求Height所有子区间内最小值的和。

事实上这是一个经典的利用DP做的问题，求解一个序列中任意子区间的最小值的和，设置L\[i\]表示最左端的大于a\[i\]的下标，R\[i\]表示最右端的大于等于a\[i\]的下标，注意需要左闭右开，然后在求出来之后对于每个位置，对答案的贡献就是 a\[i\] \* (i - L\[i\] + 1) \* (R\[i\] - i + 1)

注意事项:在拼接字符串的过程中，需要在两字符串中间增加一个'z' + 1的字符，防止出现取到的相同子串跨越两个被拼接的字符串

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)  
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)  
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    typedef vector<int> VI;
    int read(){
        int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
        if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 4e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    const int SP = 20; 
    int M,K,l1,l2,l;
    char str[maxn]; 
    int sa[maxn],rak[maxn],tex[maxn],tp[maxn],Height[maxn];
    void Qsort(int N){
        for(int i = 0; i <= M ; i ++) tex[i] = 0;
        for(int i = 1; i <= N ; i ++) tex[rak[i]]++;
        for(int i = 1; i <= M ; i ++) tex[i] += tex[i - 1];
        for(int i = N; i >= 1 ; i --) sa[tex[rak[tp[i]]]--] = tp[i];
    }
    void SA(char *str,int N){
        for(int i = 1; i <= N ; i ++) rak[i] = str[i] - '0' + 1,tp[i] = i;
        Qsort(N);    
        for(int w = 1,p = 0; p < N; M = p, w <<= 1){
            p = 0;
            for(int i = 1; i <= w; i ++) tp[++p] = N - w + i;
            for(int i = 1; i <= N ; i ++) if(sa[i] > w) tp[++p] = sa[i] - w;
            Qsort(N);
            swap(rak,tp);
            rak[sa[1]] = p = 1;
            for(int i = 2; i <= N ; i ++){
                rak[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w])?p:++p;
            }
        }
    }
    void GetHeight(char *str,int N){
        int j,k = 0;
        for(int i = 1; i <= N ; i ++){
            if(k) k--;
            int j = sa[rak[i] - 1];
            while(i + k <= N && j + k <= N && str[i + k] == str[j + k]) k++;
            Height[rak[i]] = k;
        }
    }
    LL L[maxn],R[maxn];
    LL work(int* a,int n){
        for(int i = 1; i <= n ; i ++){
            L[i] = i;
            while(L[i] != 1 && a[i] < a[L[i] - 1]) L[i] = L[L[i] - 1];
        }
        for(int i = n; i >= 1; i --){
            R[i] = i;
            while(R[i] != n && a[i] <= a[R[i] + 1]) R[i] = R[R[i] + 1];
        }
        LL ans = 0;
        for(int i = 1; i <= n ; i ++){
            ans += a[i] * ((R[i] - i + 1) * (i - L[i] + 1));
        }
        return ans;
    }
    int main(){
        scanf("%s",str + 1); l1 = strlen(str + 1);
        str[l1 + 1] = 'z' + 1;
        scanf("%s",str + 2 + l1); l2 = strlen(str + 2 + l1);
        l = l1 + l2 + 1;
        M = 122; SA(str,l);
        LL ans = 0; GetHeight(str,l);
        ans += work(Height + 1,l - 1);
        M = 122; SA(str,l1);
        GetHeight(str,l1);
        ans -= work(Height + 1,l1 - 1);
        M = 122; SA(str + l1 + 1,l2);
        GetHeight(str + l1 + 1,l2);
        ans -= work(Height + 1,l2 - 1);
        Prl(ans);
        return 0;
    }

转载于:https://www.cnblogs.com/Hugh-Locke/p/11296337.html

[https_www.luogu.org_problem_P3181]: https://www.luogu.org/problem/P3181