广义后缀自动机
<pre><code class="language-cpp">#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
namespace suffix_automata{
int maxlen[maxn], trans[maxn][26], link[maxn], size = 1;
// int sizes[maxn], ru[maxn];
inline int insert(int ch, int last){
ch -= 'a';
if(trans[last][ch]){
int p = last, x = trans[p][ch];
if (maxlen[p] + 1 == maxlen[x]){
// sizes[x] = 1;
return x;
}else{
int y = ++size;
maxlen[y] = maxlen[p] + 1;
for (int i = 0; i < 26; ++i)
trans[y][i] = trans[x][i];
while (p && trans[p][ch] == x)
trans[p][ch] = y, p = link[p];
link[y] = link[x], link[x] = y;
// sizes[y] = 1;
return y;
}
}
int z = ++size, p = last;
maxlen[z] = maxlen[last] + 1;
while (p && !trans[p][ch])
trans[p][ch] = z, p = link[p];
if (!p)
link[z] = 1;
else{
int x = trans[p][ch];
if (maxlen[p] + 1 == maxlen[x])
link[z] = x;
else{
int y = ++size;
maxlen[y] = maxlen[p] + 1;
for (int i = 0; i < 26; ++i)
trans[y][i] = trans[x][i];
while (p && trans[p][ch] == x)
trans[p][ch] = y, p = link[p];
link[y] = link[x], link[z] = link[x] = y;
}
}
// sizes[z] = 1;
return z;
}
ll cal(){
ll ans = 0;
// queue<int>Q;
// for(int i = 2; i <= size; ++i) ++ru[link[i]];
// for(int i = 1; i <= size; ++i){
// if(!ru[i]) Q.push(i);
// }
// while(!Q.empty()){
// int x = Q.front();
// Q.pop();
// sizes[link[x]] += sizes[x];//分开更新
// if(!(--ru[link[x]])) Q.push(link[x]);
// }
for(int i = 2; i <= size; i++) ans += maxlen[i] - maxlen[link[i]];
return ans;
}
};</code></pre>