2018牛课多校第一场 I-Substring（后缀数组SA）详

朴灿烈づ我的快乐病毒、 2022-05-19 11:27 110阅读 0赞

[传送门][Link 1]

思路：让你从长度为n的串中找出不同构的所有子串个数，同构的意思就是有a、b、c分别对应一种映射。那么也就是说对于一个包含不止一种字符的串来说，他可以有六种同构的串。如果一个串中包含这六种同构子串，那么也就只能算一种。那问题就是在这个串的中，对于某一类子串，不一定存在几种同构体。假如我们对这个串用这六种映射派生出6种串，组成一个大串， 那么原先串出现的每一类串，必然在大串中有6种同构体。所以找出一共多少种不同的串，然后除6。

当然还有一种特殊情况考虑到。就是当字串只包含一个字符，那只能包含3种同构体。所以这种情况应该是除3

设 mul为字串总的数， sigl为单个字符的数。得到式子是：

![ans=(mul-sigl)/6+sigl/3=(mul+sigl)/6][ans_mul-sigl_6_sigl_3_mul_sigl_6]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int INF=1<<30;
    const int N=5e4+10;
    int n, mo[6][3]={1,2,3, 1,3,2, 3,1,2, 2,1,3, 3,2,1, 2,3,1};
    char str[N];
    int t1[6*N], t2[6*N], c[6*N];
    bool cmp(int *r, int a, int b, int l){
        return r[a]==r[b] && r[a+l]==r[b+l];
    }
    
    void da(int  str[], int sa[], int rk[], int height[], int n, int m){
        n++;
        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]=str[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]]=cmp(y, sa[i-1], sa[i], j) ? p-1:p++;
            if(p>=n) break;
            m=p;
        }
        int k=0;
        n--;
        for(i=0; i<=n; i++) rk[sa[i]]=i;
        for(i=0; i<n; i++){
            if(k) k--;
            j=sa[rk[i]-1];
            while(str[i+k]==str[j+k]) k++;
            height[rk[i]]=k;
        }
    }
    int rk[6*N], height[6*N], sa[6*N];
    int s[6*N], cnt=0;
    
    ll cal_mul(){
    
        ll ans=0;
        for(int i=1; i<cnt; i++){
            ans+=n-(sa[i]%(n+1))- height[i];//每一个后缀产生的串数-前面重复的串数
        }
        return ans;
    }
    
    ll cal_sig(){
        ll ans=0, cnt=0;
        char pre=0;
    
        for(int i=0; str[i]; i++){
            if(str[i]==pre)
                cnt++;
            else{
                pre=str[i];
                ans=max(ans, cnt);//只要算出最大的串，他的长度*3就是单字符子串个数
                cnt=1;
            }
        }
        ans=max(cnt, ans);
        return ans*3ll;
    }
    
    int main(){
        while(~scanf("%d", &n)){
            cnt=0;
            scanf("%s", str);
    
            for(int i=0; i<6; i++){
    
                for(int j=0; str[j]; j++){
                    s[cnt++]=mo[i][str[j]-'a'];
                }
                s[cnt++]=4+i;
            }
    //这里一开始遇到一个问题，我把s[cnt-1]设为0就错了，不知道为什么，求解orz。
            da(s, sa, rk, height, cnt, 10);
            ll ans=0, all, sigl;
    
            all=cal_mul();
            sigl=cal_sig();
    
            ans=(all+sigl)/6ll;
    
            printf("%lld\n", ans);
        }
    
    
        return 0;
    }

[Link 1]: https://www.nowcoder.com/acm/contest/139/I
[ans_mul-sigl_6_sigl_3_mul_sigl_6]: https://private.codecogs.com/gif.latex?ans%3D%28mul-sigl%29/6&plus;sigl/3%3D%28mul&plus;sigl%29/6