Luogu P2408 不同子串个数【SAM】

P2408 不同子串个数

计算一个字符串的不同子串个数

两种方法，一种是\(dp\)出来\(SAM\)从起点开始的路径数量

另一种方法就是计算每个点的\(len[i]-len[link[i]]\)这个计算的就是这个等价类的不同串的数量

//#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 = 2e5+7;

using LL = int_fast64_t;

struct SAM{

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

    LL f[MAXN];

    void init(){ tot = last = 0; link[tot] = -1; memset(ch,0,sizeof(ch)); memset(f,0,sizeof(f)); }

    void extend(int c){

        int np = ++tot, p = last;

        len[np] = len[p] + 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];

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

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

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

                    ch[p][c] = clone;

                    p = link[p];

                }

            }

        }

        last = np;

    }

    void dfs(int u = 0){

        f[u] = 1;

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

            if(!ch[u][i]) continue;

            if(!f[ch[u][i]]) dfs(ch[u][i]);

            f[u] += f[ch[u][i]];

        }

    }

    LL query(){

        dfs(); return f[0] - 1;

        LL ret = 0; for(int i = 1; i <= tot; i++) ret += len[i] - len[link[i]]; return ret;

        //return f[0] - 1;

    }

}sam;

char s[MAXN];

void solve(){

    int n; cin >> n;

    cin >> s;

    sam.init();

    for(int i = 0, l = strlen(s); i < l; i++) sam.extend(s[i]-'a');

    cout << sam.query() << endl;

}

int main(){

    solve();

    return 0;

}

巴特西

Luogu P2408 不同子串个数【SAM】

最新文章

热门文章