# Tag-后缀自动机

Icontofig 's Blog // 我们的征程是星辰大海！Away From OI，Come to ICPC（查看友链请点About Me）

## 代码

```#include <bits/stdc++.h>
using namespace std;
struct SAM_node{
};
const int maxn = 3e5+5;
int tr[maxn][26],tot = 0,trie_id[maxn],sam_pos[maxn],cnt[maxn],root;
string s;
int n,q;
int x,l;
struct SAM{
SAM_node s[maxn<<1];
int h[maxn<<1],next[maxn<<1],to[maxn<<1];
int siz,sum,f[maxn<<1][21];
to[sum] = v;next[sum] = h[u];h[u] = sum++;
return;
}
void init(){
siz = 1;
sum = 0;
memset(h,-1,sizeof(h));
return;
}
int extend(int last,int c,int num){
int z = ++siz;
int p = last;
s[z].len = s[p].len + 1;
s[z].endpos = num;
while(p && !s[p].trans[c]){
}
if(!p)
else{
int x = s[p].trans[c];
if(s[x].len == s[p].len + 1)
else{
int y = ++siz;
s[y] = ```

## 题解

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
char ss[maxn];
typedef long long ll;
int len;
struct SAM{
int tot;
queue<int>q;
vector<int>g[maxn];
int indeg[maxn];
ll ans1;
ll ans[maxn],endpos[maxn];
int last;
void init(){
last = tot = 1;
return;
}
int extend(int ch){
int x,y,z = ++tot;
int p = last;
endpos[z] = 1;
maxlen[z] = maxlen[last] + 1;
while(p && !trans[p][ch])
if(!p){
}
else{
x = trans[p][ch];
if(maxlen[p] + 1 == maxlen[x])
else{
y = ++tot;
```

## 题解

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```
Title - Artist
0:00