51nod1469 淋漓字符串（后缀自动机）

题目大意：

首先，我们来定义一下淋漓尽致子串。

1.令原串为S。

2.设子串的长度为len，在原串S中出现的次数为k，令其出现的位置为p1， p2， ....pk(即这个子串在原串中[pi，pi + len - 1]中出现)。

3.若k=1，则该子串不是淋漓尽致子串。

4.若存在pi，pj(i != j)，使得S[pi - 1] = S[pj - 1]，则该子串不是淋漓尽致子串。

5.若存在pi，pj(i != j)，使得S[pi + len] = S[pj + len]，则该字串不是淋漓尽致字串。

否则，该子串为淋漓尽致子串。

我想知道这个串有多少个本质不同的淋漓尽致子串。

数据范围：

|S| <= 100000

S由小写字母组成。

 

题解：

建立后缀自动机，求出endpos的大小

然后endpos小于等于1的肯定不符合条件

如果endpos>1但是在slink树中有endpos>1的孩子结点也不符合条件

如果endpos>1但是可以转移其他到endpos>1的结点也不符合条件。

最后符合要求的结点代表的字符串集合，其中也只能取一个，即最大的那个maxlen（maxlen到minlen之间的也不符合要求）

（更新一下后缀自动机模板，原来的太长了）

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = 1e5 + ;

const int maxn2 = maxn*;

int cnt = , last = ;

int endpos[maxn2], tr[maxn2][], par[maxn2], mx[maxn2], c[maxn2], id[maxn2], f[maxn2];

int n;

char s[maxn];

void extend(int x){

    int np = ++cnt, p = last;

    endpos[np] = ;

    mx[np] = mx[p] + ; last = np;

    while(p && !tr[p][x]) tr[p][x] = np, p = par[p];

    if(!p) par[np] = ;

    else {

        int q = tr[p][x];

        if(mx[q] == mx[p]+) par[np] = q;

        else {

            int nq = ++cnt; mx[nq] = mx[p]+;

            memcpy(tr[nq], tr[q], sizeof(tr[q]));

            par[nq] = par[q]; par[q] = par[np] = nq;

            while(p && tr[p][x] == q) tr[p][x] = nq, p = par[p];

        }

    }

}

void topsort(){

    for(int i = ; i <= cnt; i++) c[mx[i]]++;

    for(int i = ; i <= n; i++) c[i] += c[i-];

    for(int i = ; i <= cnt; i++) id[c[mx[i]]--] = i;

    for(int i = cnt; i; i--) endpos[par[id[i]]] += endpos[id[i]];

}

int main()

{

    cin>>s;

    n = strlen(s);

    for(int i = ; i < n; i++) extend(s[i]-'a');

    topsort();

    endpos[] = ;

    for(int i = cnt; i; i--) if(endpos[id[i]] > ) f[par[id[i]]] = ;

    for(int i = ; i <= cnt; i++) if(endpos[i] <= ) f[i] = ;

    for(int i = ; i <= cnt; i++)

        for(int c = ; c < ; c++)

            if(endpos[tr[i][c]] > ){

                f[i] = ;

                break;

            }

    int ans = ;

    for(int i = ; i <= cnt; i++)

        if(!f[i]) ans++;

    cout<<ans<<endl;

    return ;

}