一、后缀自动机基本概念的理解
1、首先后缀自动机的状态是由子串的endpos来决定的
子串的endpos是指一个子串可以在原字符串的哪些位置进行匹配，
endpos构成的不同集合划分成不同的状态
关于endpos的性质： s1是s2的子串当且仅当endpos(s1)属于endpos(s2)，s1不是s2的子串当前仅当endpos(s1)和endpos(s2)的交集为空
2、对于一个用endpos划分的状态，最长的子串为longest(st)，最短的为shortest(st)，对于任何包含于该状态的子串，都是longest(st)的后缀；同样，对于一个状态中的longest(st)的后缀，如果后缀的长度在longest和shortest之间，那么它就属于这个状态。
如此可以这样理解，一个endpos划分的状态，实际上是longest形成的一系列后缀
3、Link
link是将不同endpos间连接起来的边，实际上是把系列的中断相连
4、Transition function
对于一个状态，首先找到它下一个可能出现的字符有哪些，实际上就是只需要把longest后面添加一下新的字符，然后看这个新的串被哪个状态所包含
那么它的那一系列后缀也被这个状态所包含。
暴力做法 （关于endpos）
hihocoder 1441
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;
char str[], temp[];
vector<int> endpos[][];
int n; bool ok(int x, int y, int t){
int len = y-x+;
int s = t-len+;
if(s < ) return false;
for(int i = ; i < len; i++)
if(str[i+x] != str[s+i]) return false;
return true;
}
bool cmp(int x, int y, char* temp){
int len = y-x+;
if(len != strlen(temp)) return false;
for(int i = ; i < len; i++) if(str[i+x] != temp[i]) return false;
return true;
}
void print(char* str, int x, int y){
for(int i = x; i <= y; i++) cout<<str[i];
} int main(){
cin>>str;
int len = strlen(str);
for(int i = ; i < len; i++){
for(int j = i; j < len; j++)
for(int k = ; k < len; k++)
if(ok(i, j, k)) endpos[i][j].push_back(k+);
}
cin>>n;
while(n--){
cin>>temp;
PII s;
for(int i = ; i < len; i++)
for(int j = i; j < len; j++)
if(cmp(i, j, temp))
{ s = {i, j}; break; }
auto x = endpos[s.fi][s.se];
int longest = , shortest = 1e9;
PII ll, ss;
for(int i = ; i < len; i++)
for(int j = i; j < len; j++){
auto y = endpos[i][j];
if(x.size() != y.size()) continue;
int fail = ;
for(int k = ; k < x.size(); k++) if(x[k] != y[k]) fail = ;
if(fail) continue;
if(longest < j-i+) { longest = j-i+; ll = {i, j}; }
if(shortest > j-i+) { shortest = j-i+; ss = {i, j}; }
}
print(str, ss.fi, ss.se); cout<<" ";
print(str, ll.fi, ll.se); cout<<" ";
for(auto tt : x) cout<<tt<<" "; cout<<endl;
}
}
二、算法部分
hihocoder上讲的很详细
但是只是给出了实现的做法，算法的正确性并没有给出详尽的证明，以后看情况补充吧（挖坑）
算法分成三种情况。运用增量法，取上一次的状态
顺着它的link走，可以得到它的所有后缀，所以就是所有后缀加上这次新的字符
首先建立一个新的状态z代表S[1...i+1]，maxlen显然是i+1
①如果link-path上都没有这个新的字符，就全部直接连新的状态，link[z] = s，更新minlen
②如果link-path上有一个状态x，它加上新的字符可以转移到另一个状态y，做如下处理
1、如果maxlen[x]+1 = maxlen[y]，那么说明实际上x是z的longest的一系列后缀，只不过不在同一状态中，所以直接link[z] = x即可，更新minlen
2、如果maxlen[x]+1 < maxlen[y]，那么我们就把y结点分成两部分，一部分p是maxlen[y] <= maxlen[x]+1，这部分实际上和1是一样的。另一部分q是maxlen[y] > maxlen[x] + 1
实际上x并不能转移到q，所以q留在原地，新建一个结点代表p，让x连向p，然后link[p] = x, link[q] = link[z] = p。
对于剩下的link-path上的状态，如果它们连向y的话，就重新连向p。最后更新一下p的minlen
三、题目练习
hihocoder 1445
题目大意：给出一个串，求出不重复子串的个数
答案就是每个状态的longest减去shortest，可以保证没有重复的情况出现
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n = , len, st;
const int maxL = 1e6 + ;
int maxlen[*maxL], minlen[*maxL], trans[*maxL][], slink[*maxL];
int new_state(int _maxlen, int _minlen, int *_trans, int _slink){
maxlen[n] = _maxlen;
minlen[n] = _minlen;
for(int i = ; i < ; i++){
if(_trans == NULL)
trans[n][i] = -;
else
trans[n][i] = _trans[i];
}
slink[n] = _slink;
return n++;
} int add_char(char ch, int u){
int c = ch - 'a';
int z = new_state(maxlen[u]+, -, NULL, -);
int v = u;
while(v != - && trans[v][c] == -){
trans[v][c] = z;
v = slink[v];
}
if(v == -){
minlen[z] = ;
slink[z] = ;
return z;
}
int x = trans[v][c];
if(maxlen[v] + == maxlen[x]){
minlen[z] = maxlen[x] + ;
slink[z] = x;
return z;
}
int y = new_state(maxlen[v] + , -, trans[x], slink[x]);
slink[y] = slink[x];
minlen[x] = maxlen[y] + ;
slink[x] = y;
minlen[z] = maxlen[y] + ;
slink[z] = y;
int w = v;
while(w != - && trans[w][c] == x){
trans[w][c] = y;
w = slink[w];
}
minlen[y] = maxlen[slink[y]] + ;
return z;
} char str[maxL];
int main()
{
cin>>str;
st = new_state(, , NULL, -);
int len = strlen(str);
for(int i = ; i < len; i++) {
st = add_char(str[i], st);
}
long long ans = ;
for(int i = ; i < n; i++) ans += (maxlen[i] - minlen[i] + );
cout<<ans<<endl;
return ;
}
hihocoder 1449
给定一个串，要求求出长度为k的子串中重复最多的串出现的次数
问题实际上转换成了求endpos的大小
在建立完后缀自动机后，我们用link可以连接成一棵树
对于父结点的孩子若干个孩子，实际上我们有
endpos[fa] >= sigma(endpos[son])
一般情况下是等于的，但是如果这一点的状态恰好表示了一个前缀，那么就要加1
而前缀的那些点其实是加入的那些，所以加入的过程中标记一下即可
最后求答案的时候，对于一个状态我们实际上要用endpos[x]更新minlen[x] ~ maxlen[x]
但是实际上我们只需要更新maxlen，原因是答案一定是随长度递增的
所以最后做一个这样的处理 ans[i] = max(ans[i], ans[i+1]就可以了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
int n = , len, st;
const int maxL = 1e6 + ;
int maxlen[*maxL], minlen[*maxL], trans[*maxL][], slink[*maxL], lab[*maxL], ans[*maxL], son[*maxL], endpos[*maxL];
int new_state(int _maxlen, int _minlen, int *_trans, int _slink){
maxlen[n] = _maxlen;
minlen[n] = _minlen;
for(int i = ; i < ; i++){
if(_trans == NULL)
trans[n][i] = -;
else
trans[n][i] = _trans[i];
}
slink[n] = _slink;
return n++;
} int add_char(char ch, int u){
int c = ch - 'a';
int z = new_state(maxlen[u]+, -, NULL, -); lab[z] = ;
int v = u;
while(v != - && trans[v][c] == -){
trans[v][c] = z;
v = slink[v];
}
if(v == -){
minlen[z] = ;
slink[z] = ;
return z;
}
int x = trans[v][c];
if(maxlen[v] + == maxlen[x]){
minlen[z] = maxlen[x] + ;
slink[z] = x;
return z;
}
int y = new_state(maxlen[v] + , -, trans[x], slink[x]);
slink[y] = slink[x];
minlen[x] = maxlen[y] + ;
slink[x] = y;
minlen[z] = maxlen[y] + ;
slink[z] = y;
int w = v;
while(w != - && trans[w][c] == x){
trans[w][c] = y;
w = slink[w];
}
minlen[y] = maxlen[slink[y]] + ;
return z;
} char str[maxL];
int main()
{
cin>>str;
st = new_state(, , NULL, -);
int len = strlen(str);
for(int i = ; i < len; i++) {
st = add_char(str[i], st);
}
for(int i = ; i <= n; i++) son[slink[i]]++;
queue<int> Q;
for(int i = ; i <= n; i++) if(son[i] == ) Q.push(i), endpos[i] = ;
while(!Q.empty()){
int x = Q.front(); Q.pop();
if(x == ) continue;
int y = slink[x];
son[y]--; endpos[y] += endpos[x];
if(son[y] == ){
if(lab[y]) endpos[y]++;
Q.push(y);
}
}
for(int i = ; i <= n; i++) ans[maxlen[i]] = max(ans[maxlen[i]], endpos[i]);
for(int i = len-; i >= ; i--) ans[i] = max(ans[i], ans[i+]);
for(int i = ; i <= len; i++) cout<<ans[i]<<endl;
return ;
}