题目大意：
首先，我们来定义一下淋漓尽致子串。
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 + 100; const int maxn2 = maxn*2; int cnt = 1, last = 1; int endpos[maxn2], tr[maxn2][30], 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] = 1; mx[np] = mx[p] + 1; last = np; while(p && !tr[p][x]) tr[p][x] = np, p = par[p]; if(!p) par[np] = 1; else { int q = tr[p][x]; if(mx[q] == mx[p]+1) par[np] = q; else { int nq = ++cnt; mx[nq] = mx[p]+1; 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 = 1; i <= cnt; i++) c[mx[i]]++; for(int i = 1; i <= n; i++) c[i] += c[i-1]; for(int i = 1; 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 = 0; i < n; i++) extend(s[i]-'a'); topsort(); endpos[0] = 0; for(int i = cnt; i; i--) if(endpos[id[i]] > 1) f[par[id[i]]] = 1; for(int i = 1; i <= cnt; i++) if(endpos[i] <= 1) f[i] = 1; for(int i = 1; i <= cnt; i++) for(int c = 0; c < 26; c++) if(endpos[tr[i][c]] > 1){ f[i] = 1; break; } int ans = 0; for(int i = 2; i <= cnt; i++) if(!f[i]) ans++; cout<<ans<<endl; return 0; }