BZOJ3238 SA//SAM

雨点打透心脏的1/2处 2023-10-10 07:51 33阅读 0赞

> [题目链接][Link 1]

题意：求两两后缀的LCP的和

做法一：

很容易想到后缀数组，Height数组表示的是排名相邻两后缀的LCP

但是可以意识到任意两后缀的LCP是他们之间Height的最小值，所以只要计算出每个点的Height作为最小值覆盖到最左和最右的点，那么r\[i\] - i + 1--- i - l\[i\] + 1这个数量的区间形成的后缀都是以当前Height为最小值的

这是一个经典的单调栈//DP问题，两种方法都可以线性求出来，需要特别注意的是两种方法都需要注意相同Height回来带来重复计算，例如1,1,1的height，直接计算的话每个值都管到\[1,3\]，因此要作一个左闭右开或左开右闭的情况，即\[1,3\],\[2,3\],\[3,3\]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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 = 5e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,K;
    char str[maxn];
    int sa[maxn],rak[maxn],tex[maxn],tp[maxn],Height[maxn];
    void GetHeight(){
        int j,k = 0;
        for(int i = 1; i <= N ; i ++){
            if(k) k--;
            int j = sa[rak[i] - 1];
            while(str[i + k] == str[j + k]) k++;
            Height[rak[i]] = k;
        }
    } 
    void Qsort(){
        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(){
        for(int i = 1; i <= N ; i ++) rak[i] = str[i] - 'a' + 1,tp[i] = i;
        Qsort();
        for(int w = 1,p = 0; p < N; w <<= 1,M = p){
            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();
            swap(tp,rak);
            rak[sa[1]] = p = 1;
            for(int i = 2; i <= N; i ++){
                rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w])?p:++p;
            }
        }
    }
    int Stack[maxn],top;
    int l[maxn],r[maxn];
    int main(){
        scanf("%s",str + 1); N = strlen(str + 1);
        M = 122;
        SA(); GetHeight();
        for(int i = 1; i <= N ; i ++){
            while(top && Height[Stack[top]] > Height[i]) top--;
            l[i] = Stack[top] + 1;
            Stack[++top] = i;
        }
        top = 0; Stack[0] = N + 1;
        for(int i = N; i >= 1; i --){
            while(top && Height[Stack[top]] >= Height[i]) top--;
            r[i] = Stack[top] - 1;
            Stack[++top] = i;
        }
        LL sum = 1ll * (N - 1) * (1 + N) * N / 2;
        for(int i = 1; i <= N; i ++){
            //cout << l[i] << " " << r[i] << endl;
            sum -= 1ll * 2 * (r[i] - i + 1) * (i - l[i] + 1) * Height[i];
        }
        Prl(sum);
        return 0;
    }

做法二：

SAM一个重要的性质就是parent树上，两节点的最长公共后缀是他们LCA表示的最长字符串

所以我们将字符串逆转，就变成了求N个代表前缀的关键点两两之间的len\[LCA\]的和，事实上right数组表示的就是子树下有多少关键点，

所以可以每个点的关键点对数就是num\[u\] \* (num\[u\] - 1) - Σnum\[v\] - (num\[v\] - 1) (v 为 u的儿子)

对数可以O(n)求出，最后统计的时候减去对数 \* len\[i\]即可。

也可以用num\[i\] \* (num\[i\] - 1) \* (len\[i\] - len\[fa\[i\]) 作为减去的贡献，理解起来稍微抽象一点，就是计入所有贡献之后减去LCA为父亲及以上的点的贡献

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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 = 5e5 + 10;
    const int maxc = 26;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,K;
    int len[maxn << 1],fa[maxn << 1],son[maxn << 1][maxc];
    LL num[maxn << 1];
    int size,last;
    LL sum;
    void Init(){
        size = last = 1;
    }
    void insert(char c){
        int s = c - 'a';
        int p = last,np = ++size;last = np; 
        //cout << np << endl;
        len[np] = len[p] + 1; num[np] = 1; 
        for(;p && !son[p][s]; p = fa[p]) son[p][s] = np;
        if(!p) fa[np] = 1;
        else{
            int q = son[p][s];
            if(len[p] + 1 == len[q]) fa[np] = q;
            else{
                int nq = ++size; len[nq] = len[p] + 1;
                memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq] = fa[q]; fa[q] = fa[np] = nq; 
                for(;son[p][s] == q && p;p = fa[p]) son[p][s] = nq;
            }
        }
    }
    int A[maxn << 1],tmp[maxn << 1];
    void Qsort(){
        for(int i = 1; i <= size; i ++) tmp[len[i]]++;
        for(int i = 1; i <= size; i ++) tmp[i] += tmp[i - 1];
        for(int i = 1; i <= size; i ++) A[tmp[len[i]]--] = i;
    }
    char str[maxn];
    LL dp[maxn << 1];
    int main(){
        scanf("%s",str); N = strlen(str);
        reverse(str,str + N);
        sum = 1ll * (N - 1) * (N + 1) * N / 2; Init();
        for(int i = 0 ; i < N ; i ++) insert(str[i]);
        Qsort();
        for(int i = size; i >= 1; i --) num[fa[A[i]]] += num[A[i]];
        for(int i = 2; i <= size; i ++){
            sum -= (len[i] - len[fa[i]]) * num[i] * (num[i] - 1);
        }
    //    for(int i = 2; i <= size; i ++) sum -= len[i] * dp[i];
        Prl(sum);
        return 0;
    }

SAM

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

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=3238
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif