Nowcoder Mutischool-training 4 C Counting New String 广义后缀自动机

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题目大意

对S串做两次f变换,得到一个字符串集A,求A中本质不同的字符串数量。

题解

其实不管是观察,还是拿样例手算,最后一定能得出一个结论:

其实两次f变换和一次f变换的作用是一样的。

所以只需要看一下一次f变换就行了。

f其实是对子串的变换,后面被变换的字符只跟其前面的字典序比他大的字符有关。

先看题目要求,求A中本质不同的字符串数量。

前面说了A实际上是S的所有子串做了变换而已。所以也就是本质不同的类子串数量(这个说法大概可以吧)。所以很自然想到这是一个后缀自动机。

但是这里的要求的并不是简单的子串,需要做变化。

前面说了,被变换的字符只跟其前面的字典序比他大的字典序最大的字符有关,只要出现一个比他大的字符就要重新更新字符串。

于是我们可以这样搞:

我们考虑将原串倒过来,然后按照题目的要求去建一个Trie,具体建法比较麻烦,如果当前字符的上一个比他大的字符没有出现,则需要从根开始往下重新建一条链,否则就继续往下建,复杂度最大为O(10n),但实际上肯定到不了。

然后对Trie静态建广义后缀自动机,直接跑本质不同子串数量即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6+5;
string s;
char ss[maxn];
int len;
int son[maxn][10],fa[maxn],cl[maxn];
int now = 1;
int root = 1;
struct SAM{
    int tot;
    int pos[maxn],link[maxn],maxlen[maxn],trans[maxn][10];
    queue<int>q;
    ll ans;
    void init(){
        tot = 1;
        return;
    }
    int extend(int ch,int last){
        int x,y,z = ++tot;
        int p = last;
        maxlen[z] = maxlen[last]+1;
        while(p && !trans[p][ch])
            trans[p][ch] = z,p = link[p];
        if(!p)link[z] = 1;
        else{
            x = trans[p][ch];
            if(maxlen[p] + 1 == maxlen[x])
                link[z] = x;
            else{
                y = ++tot;
                maxlen[y] = maxlen[p] + 1;
                for(int i = 0;i < 10;++i)
                    trans[y][i] = trans[x][i];
                while(p && trans[p][ch] == x){
                    trans[p][ch] = y;
                    p = link[p];
                }
                link[y] = link[x];
                link[z] = link[x] = y;
            }
        }
        return z;
    }
    void build(){
        for(int i = 0;i < 10;++i){
            if(son[1][i])
                q.push(son[1][i]);
        }
        pos[1] = 1;
        while(!q.empty()){
            int x = q.front();
            q.pop();
            pos[x] = extend(cl[x],pos[fa[x]]);
            for(int i = 0;i < 10;++i)
                if(son[x][i])
                    q.push(son[x][i]);
        }
    }
    void calc_sub_num(){
        ans = 0;
        for(int i = 2;i <= tot;++i){
            ans += (ll)(maxlen[i] - maxlen[link[i]]);
        }
        return;
    }
}M;
int last;
int pos[12];
int p[maxn];
void add_trie(int c){
    if(son[last][c])return;
    son[last][c] = ++now;
    cl[now] = c;
    fa[now] = last;
    return;
}
int main(){
    cin >> s;
    len = s.size();
    for(int i = 1;i <= len;++i){
        ss[i] = s[i-1];
    }
    reverse(ss+1,ss+len+1);
    p[0] = 1;
    for(int i = 1;i <= len;++i){
        int c = ss[i] - 'a';
        int q = pos[c];
        last = p[q];
        for(int j = q+1;j <= i;++j){
            add_trie(c);
            last = now;
            p[j] = last;
        }
        pos[c] = i;
        for(int j = 0;j < c;++j)
            pos[j] = max(pos[j],i);
    }
    M.init();
    M.build();
    M.calc_sub_num();
    cout << M.ans << endl;
    return 0;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00