HDU4622 Reincarnation【SAM】

HDU4622 Reincarnation

给出一个串，每次询问其一个子串有多少不同的子串

按每个后缀建立\(SAM\)不断往后加字符，然后记录答案，查询的时候直接用即可

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 4444;

int res[MAXN][MAXN];

char s[MAXN];

struct SAM{

    int len[MAXN],link[MAXN],ch[MAXN][26],ret,tot,last;

    void init(){

        memset(ch,0,sizeof(ch));

        link[tot = last = 0] = -1;

        ret = 0;

    }

    void extend(int c){

        int np = ++tot, p = last;

        len[np] = len[last] + 1;

        while(p!=-1 and !ch[p][c]){

            ch[p][c] = np;

            p = link[p];

        }

        if(p==-1) link[np] = 0;

        else{

            int q = ch[p][c];

            if(len[p]+1==len[q]) link[np] = q;

            else{

                int clone = ++tot;

                len[clone] = len[p] + 1;

                link[clone] = link[q];

                ret += len[clone] - len[link[clone]];

                memcpy(ch[clone],ch[q],sizeof(ch[q]));

                ret -= len[q] - len[link[q]];

                link[q] = link[np] = clone;

                ret += len[q] - len[link[q]];

                while(p!=-1 and ch[p][c]==q){

                    ch[p][c] = clone;

                    p = link[p];

                }

            }

        }

        last = np;

        ret += len[np] - len[link[np]];

    }

}sam;

void solve(){

    cin >> s;

    int n = strlen(s);

    for(int i = 0; i < n; i++){

        sam.init();

        for(int j = i; j < n; j++){

            sam.extend(s[j]-'a');

            res[i][j] = sam.ret;

        }

    }

    int q; cin >> q;

    while(q--){

        int l, r; cin >> l >> r;

        cout << res[l-1][r-1] << endl;

    }

}

int main(){

    ____();

    int T;

    for(cin >> T; T; T--) solve();

    return 0;

}

巴特西

HDU4622 Reincarnation【SAM】

最新文章

热门文章