526互联

The 2023 ICPC Asia EC Regionals Online Contest (I) B.String

发布时间 2023-10-08 11:11:48作者: Fighoh

The 2023 ICPC Asia EC Regionals Online Contest (I)B.String

题意：

给定等长字符串\(S_1,S_2\)，下标从\(1\)开始

给出\(q\)个询问，每次给出一个字符串\(T\)

每次询问计算出三元组数量\((i, j, k)(1\le i\le j< k\le |S_1|)\)，需要满足条件\(S_1[i,j]+S_2[j + 1, k] = T\)

数据范围：

\(1\le |S_1|=|S_2|\le 1e5 ,\quad 1\le q \le 2e5,\quad 1\le |T|\le2e5,\quad \sum{|T|\le2e5}\)

Solution

\(Hint1\) 容易想到，肯定是要枚举\(j\)的位置，思考一下\(S_1[i,j]\)是什么，这是\(S_1[1,j]\)的后缀，也就是\(S_1\)的前缀的后缀，如果我们只要求\(S_1[i,j]\)在\(S_1\)中的出现次数，这可以用后缀自动机进行统计，其数量就是\(S_1[i,j]\)对应的\(endpos\)所在的状态所有通过后缀链接连到该状态的那些状态中不是\(Copy\)出来的状态的数量，换句话说就是后缀自动机通过后缀链接建出来的\(parent\)树，\(S_1[i,j]\)的数量就是自动机上走到对应状态后，其子树中所有实点的数量，这可以通过\(dfs\)预处理出来。

\(Hint2\) 那么\(S_2[j + 1, k]\)其实也可以看成是\(S_2\)的反串建出来的一棵\(parent\)树，那么此时我们去枚举\(j\)在\(T\)中的位置，假设是\(x\)，是不是只要找到\(T[1,x]\)和\(T[x + 1, |T|]\)在两个\(parent\)树上对应的子树，在这两棵子树中公共点(准确来说这两个状态在\(S\)中下标分别为\(j,j+1\))的个数就是在\(T\)在这个位置断开能够在找到的三元组数量，也就是子树交的问题。

\(Hint3\) 子树交其实就是二维数点的问题，可以直接用主席树进行统计，首先我们得把子树交转化成线段交的问题，利用\(dfn\)序即可，然后我们以\(S_1\)的\(dfn\)序为版本，\(S_2\)的\(dfn\)序为线段树中的下标，维护对应状态的数量即可，也就是说我们在每个版本中更新时在对应状态在线段树中进行单点加即可，这样我们询问时只要找到\(T\)的每一个前缀在\(S_1\)的后缀自动机中的对应状态以及\(T\)的每一个后缀在\(S_2\)的后缀自动机中的对应状态，然后我们从前往后遍历每次统计相交的数量即可。

Code

struct SAM {
    vector<vector<int> >nxt;//转移
    vector<int>len;//长度
    vector<int>link;//后缀链接
    int last,cnt;//上一个状态和状态数总数
    void init(int strlen,int chrsize){//字符串大小，字符集大小
        // len.clear();link.clear();nxt.clear();
        last=cnt=1;//初始状态空集
        len.resize(1+strlen<<1,0);
        link.resize(1+strlen<<1,0);
        nxt.resize(1+strlen<<1,vector<int>(chrsize,0));
    }
    void add(string s){
        for(auto i:s)
            add(i - 'a');
    }
    void add(int c){
        int p=last,cur=++cnt;
        len[cur]=len[p]+1;
        //情况1 直接扩展
        while(p&&!nxt[p][c]){
            nxt[p][c]=cur;
            p=link[p];
        }
        last=cur;
        if(!p)link[cur]=1;
        else{
            int q=nxt[p][c];
            //情况2-A 建立新的后缀链接
            if(len[q]==len[p]+1)link[cur]=q;
            //情况2-B 拆点建立
            else{
                int cl=++cnt;
                len[cl]=len[p]+1;
                nxt[cl]=nxt[q],link[cl]=link[q];
                link[cur]=link[q]=cl;
                while(p&&nxt[p][c]==q){
                    nxt[p][c]=cl;
                    p=link[p];
                }
            }
        }
    }
    vector<vector<int>> G;
    void build() {
        G.resize(cnt + 1);
        for (int i = 2; i <= cnt; ++i) {
            G[link[i]].pb(i);
        }
    }
    vector<int> in, out;
    int idx;
    void dfs(int u) {
        in[u] = ++idx;
        for (auto v : G[u])
            dfs(v);
        out[u] = idx;
    }
    void getDfn() {
        in.resize(cnt + 1);
        out.resize(cnt + 1);
        dfs(1);
    }
} sam_s1, sam_s2;
int root[maxn];
struct SegTree {
#define mid (l + r >> 1)
    int sum[maxn << 5], ls[maxn << 5], rs[maxn << 5], idx;
    void ins(int p, int &np, int l, int r, int pos) {
        np = ++idx;
        ls[np] = ls[p], rs[np] = rs[p], sum[np] = sum[p] + 1;
        if (l == r) return ;
        if (pos <= mid) ins(ls[p], ls[np], l, mid, pos);
        else ins(rs[p], rs[np], mid + 1, r, pos);
    }
    int query(int p, int np, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return sum[np] - sum[p];
        int res = 0;
        if (ql <= mid) res += query(ls[p], ls[np], l, mid, ql, qr);
        if (mid < qr) res += query(rs[p], rs[np], mid + 1, r, ql, qr);
        return res;
    }
#undef mid
} seg;
void solve()  {
    string s1, s2; cin >> s1 >> s2;
    int n = s1.length();
    sam_s1.init(n, 26), sam_s2.init(n, 26);
    vector id(2, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        sam_s1.add(s1[i] - 'a');
        id[0][i] = sam_s1.last;
    }
    for (int i = n - 1; i >= 0; --i) {
        sam_s2.add(s2[i] - 'a');
        id[1][i] = sam_s2.last;
    }
    sam_s1.build(); sam_s2.build();
    sam_s1.getDfn(); sam_s2.getDfn();
    vector<int> vec(sam_s1.idx + 1);
    for (int i = 0; i < n - 1; ++i) {
        vec[sam_s1.in[id[0][i]]] = sam_s2.in[id[1][i + 1]];
    }
    for (int i = 1; i <= sam_s1.idx; ++i) {
        seg.ins(root[i - 1], root[i], 1, sam_s2.idx, vec[i]);
    }
    int q; cin >> q;
    while (q--) {
        string t; cin >> t;
        int m = t.length();
        vector p(2, vector<int>(m));
        int now = 1;
        for (int i = 0; i < m; ++i) {
            now = sam_s1.nxt[now][t[i] - 'a'];
            p[0][i] = now;
        }
        now = 1;
        for (int i = m - 1; i >= 0; --i) {
            now = sam_s2.nxt[now][t[i] - 'a'];
            p[1][i] = now;
        }
        ll ans = 0;
        for (int i = 0; i < m - 1; ++i) {
            if (!p[0][i] || !p[1][i + 1]) continue;
            ans += seg.query(root[sam_s1.in[p[0][i]] - 1], root[sam_s1.out[p[0][i]]], 1, sam_s2.idx,
                             sam_s2.in[p[1][i + 1]], sam_s2.out[p[1][i + 1]]);
        }
        cout << ans << '\n';
    }
}