HDU – 4622 Reincarnation 后缀自动机

Reincarnation 后缀自动机

 Source

HDU - 4622

My Solution

题意：给出一个长度<=2000的字符串，然后给出q<=10000个询问，为s[l,r]内有多少个不同的子串。

后缀自动机

首先n <= 2000，故可以用O(n^2)的算法，故对于每个 i ~ n-1建立n个后缀自动机，每次添加一个字符就多出val[np] - val[pre[np]]个不同的子串，

valx]表示x节点存储的字符串个数即能表示的最长子串。

故用sum[maxn][maxn] n个前缀和来存储区间内不同子串的个数。

复杂度 O(n^2)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2*2e3 + 8;

string s;
struct SAM{
    int ch[maxn][26], pre[maxn], val[maxn];
    int last, tot;
    void init(){
        last = tot = 0;
        memset(ch[0], -1, sizeof ch[0]);
        pre[0] = -1; val[0] = 0;
    }
    int extend(int c){
        int p = last, np = ++tot;
        val[np] = val[p] + 1;
        memset(ch[np], -1, sizeof ch[np]);
        while(~p && ch[p][c] == -1) ch[p][c] = np, p = pre[p];
        if(p == -1) pre[np] = 0;
        else{
            int q = ch[p][c];
            if(val[q] != val[p] + 1){
                int nq = ++tot;
                memcpy(ch[nq], ch[q], sizeof ch[q]);
                val[nq] = val[p] + 1;
                pre[nq] = pre[q];
                pre[q] = pre[np] = nq;
                while(~p && ch[p][c] == q) ch[p][c] = nq, p = pre[p];
            }
            else pre[np] = q;
        }
        last = np;
        return val[np] - val[pre[np]];
    }
} sam;

int sum[maxn][maxn];

int main()
{
    #ifdef LOCAL
    freopen("13.in", "r", stdin);
    //freopen("13.out", "w", stdout);

    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);
    int T, n, i, j, q;
    cin >> T;
    while(T--){
        cin >> s;
        n = s.size();
        for(i = 0; i < n; i++){
            sam.init(); sum[i+1][0] = 0;
            for(j = i; j < n; j++) sum[i+1][j+1] = sum[i+1][j] + sam.extend(s[j] - 'a'); } cin >> q;
        while(q--){
            cin >> i >> j;
            cout << sum[i][j] << "n";
        }
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx