# Nowcoder Mutischool-training 4 C Counting New String 广义后缀自动机

## 题解

f其实是对子串的变换，后面被变换的字符只跟其前面的字典序比他大的字符有关。

## 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6+5;
string s;
char ss[maxn];
int len;
int son[maxn][10],fa[maxn],cl[maxn];
int now = 1;
int root = 1;
struct SAM{
int tot;
queue<int>q;
ll ans;
void init(){
tot = 1;
return;
}
int extend(int ch,int last){
int x,y,z = ++tot;
int p = last;
maxlen[z] = maxlen[last]+1;
while(p && !trans[p][ch])
trans[p][ch] = z,p = link[p];
else{
x = trans[p][ch];
if(maxlen[p] + 1 == maxlen[x])
else{
y = ++tot;
maxlen[y] = maxlen[p] + 1;
for(int i = 0;i < 10;++i)
trans[y][i] = trans[x][i];
while(p && trans[p][ch] == x){
trans[p][ch] = y;
}
}
}
return z;
}
void build(){
for(int i = 0;i < 10;++i){
if(son[1][i])
q.push(son[1][i]);
}
pos[1] = 1;
while(!q.empty()){
int x = q.front();
q.pop();
pos[x] = extend(cl[x],pos[fa[x]]);
for(int i = 0;i < 10;++i)
if(son[x][i])
q.push(son[x][i]);
}
}
void calc_sub_num(){
ans = 0;
for(int i = 2;i <= tot;++i){
ans += (ll)(maxlen[i] - maxlen[link[i]]);
}
return;
}
}M;
int last;
int pos[12];
int p[maxn];
if(son[last][c])return;
son[last][c] = ++now;
cl[now] = c;
fa[now] = last;
return;
}
int main(){
cin >> s;
len = s.size();
for(int i = 1;i <= len;++i){
ss[i] = s[i-1];
}
reverse(ss+1,ss+len+1);
p[0] = 1;
for(int i = 1;i <= len;++i){
int c = ss[i] - 'a';
int q = pos[c];
last = p[q];
for(int j = q+1;j <= i;++j){
last = now;
p[j] = last;
}
pos[c] = i;
for(int j = 0;j < c;++j)
pos[j] = max(pos[j],i);
}
M.init();
M.build();
M.calc_sub_num();
cout << M.ans << endl;
return 0;
}