对于一个关于只接受 \(str\) 后缀的后缀自动机，其后缀肯定能从起始状态 \(S\) 合理地转移，而非后缀必然无法转移
定义
定义相关的函数
\(trans[u][ch]=v\)：表示 \(u\) 状态沿着 \(ch\) 边转移到了 \(v\) 状态的转移函数
\(endpos(s)\)：表示 \(str\) 的任意子串 \(s\) 的终止位置集合，用于子串归类
性质 1：当 \(len(s1) \le len(s2)\) 且 \(endpos(s1)\) 包含 \(endpos(s2)\) 所有子集时，\(s2\) 是 \(s1\) 的后缀（充要）
当两个集合 \(endpos(s1)==endpos(s2)\)，则认为子串 \(s1\) 和 \(s2\)属 于同一类
对于每一个相同的归类都设为一个状态，假定其中一个为 \(u\)
\(substr(u)\)：表示归为同一状态 \(u\) 的所有子串集合
\(longest(u)\)：\(substr(u)\) 中最长的子串
\(shortest(u)\)：\(substr(u)\) 中最短的子串
性质 2：\(substr(u)\) 中每一个子串 \(s\) 都是 \(longest(u)\) 的后缀；\(longest(u)\) 的后缀中满足\(len(s) \le len(shortest(u))\) 的都属于状态\(u\)，即 \(substr(u)\)
有了前面的东西就可以考虑一定的优化如下
\(slink[u]=v\)：我们用 suffix link 来表示不属于该状态的 \(longest(u)\) 的后缀（由性质 1，由于长度小而无法表示不包含的 \(endpos\) 则用 \(slink\) 连接起来，直到起始状态 \(S\) 为止；\(slink[u]=v\) 的沿向一定是 \(endpos(v)\) 逐渐包含 \(endpos(u)\) 的过程，而 \(endpos(S)\) 则包含所有位置）
\(minlen[u],maxlen[u]\)：分别表示状态 \(u\) 中最短和最长的字符串的长度（由性质 2，这些都是连续的后缀，无需多余记录真实的字符串）
为此我们用 \(slink\) 替代了 \(endpos\)，同时 \(minlen,maxlen\) 替代了 \(substr,shortest,longest\)
构造过程
- 考虑增量法，假设已经构造好 \(str[1...i]\) 的后缀自动机，如何在线增加一个 \(str[i+1]\)（设为 \(ch\)）以满足 \(str[j...i+1],1 \le j \le i+1\) 的构造
- 至少 \(str[1...i+1]\) 肯定没有重复的出现在原有的任一状态中，假设新增的状态为 \(u\)，令 \(str[1...i]\) 所在的状态 \(v\)（此前最后一个新增的状态）新增转移 \(trans[v][ch]=u\)（此时也表示了 \(str[j...i],1 \le j \le n-minlen(u)+1\) 的转移），并沿着 \(slink[v]=w\) 的路径，对所有的 \(trans[w][ch]=null\)都把对应转移指向\(u\)
- 对于第一个已经存在先前的状态 \(x\) 满足 \(trans[w][ch]=x\) 的情况，需要分两类考虑
- 一类是 \(maxlen[w]+1=maxlen[x]\)，此时表明该状态 \(x\) 完全重复且无多余地覆盖了 \(str[j...i+1]\) 的后缀，那么只需 \(slink[u]=x\)，结束流程
- 另一类是 \(maxlen[w]+1 \lt maxlen[x]\)，此时需要划分原有的 \(x\) 的子串为三个部分，\(minlen[x]...maxlen[w]+1...maxlen[x]\)，考虑把状态 \(x\) 拆分出一部分 \(y\) 来继承原有 \([minlen[w],maxlen[w]+1]\) 的部分，\(x\) 只包含剩下的部分（此时 \(slink[y]=slink[x],slink[x]=y\)），那么状态 \(y\) 的出现使得问题回归到上一类的情况，只需 \(trans[w][ch]=y,slink[u]=y\)
- 对于上面的转移可能不止一个 \(w\) 转移向原 \(x\)，所以需要把连续的 \(trans[w][ch]\) 置为 \(y\)
完成版
#include<bits/stdc++.h>
#define fast_io() do{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}while(0)
using namespace std;
namespace util {
template<typename T>
inline void alloc(vector<T> &v) {
v.emplace_back();
}
template<typename T>
inline void empb(vector<T> &v,T &arg) {
v.emplace_back(arg);
}
}
using namespace util;
struct SuffixAutomaton {
vector<array<int,26>> trans;
vector<int> slink,minlen,maxlen;
int last;
inline void init() {
alloc(trans);
alloc(slink);
alloc(minlen);
alloc(maxlen);
}
SuffixAutomaton() {
init();
last = 0;
slink[0] = -1;
minlen[0] = maxlen[0] = 0;
trans[0].fill(-1);
}
int state(int tr,int suf,int mn,int mx) {
int cur = trans.size();
alloc(trans);
if(~tr) trans[cur] = trans[tr];
else trans[cur].fill(-1);
empb(slink,suf);
empb(minlen,mn);
empb(maxlen,mx);
return cur;
}
int add(char ch) {
int c = ch - 'a';
int u = state(-1,-1,-1,maxlen[last]+1);
int v = last;
while(v!=-1 && trans[v][c] == -1) {
trans[v][c] = u;
v = slink[v];
}
if(v == -1) {
minlen[u] = 1;
slink[u] = 0;
return last = u;
}
int x = trans[v][c];
if(maxlen[v]+1 == maxlen[x]) {
slink[u] = x;
minlen[u] = maxlen[x]+1;
return last = u;
}
int y = state(x,-1,-1,maxlen[v]+1);
minlen[y] = maxlen[slink[y] = slink[x]]+1;
minlen[x] = maxlen[slink[x] = y]+1;
minlen[u] = maxlen[slink[u] = y]+1;
while(v != -1 && trans[v][c] == x) {
trans[v][c] = y;
v = slink[v];
}
return last = u;
}
};
int main() {
fast_io();
string str;
cin >> str;
SuffixAutomaton sam;
for(int i = 0; str[i]; i++) {
sam.add(str[i]);
}
long long res = 0;
for(int i = 1; i < sam.trans.size(); i++) {
res += sam.maxlen[i]-sam.minlen[i]+1;
}
cout << res << endl;
return 0;
}
old version: https://paste.ubuntu.com/p/TjFs5wVS8d/
参考
hihocoder127/128解题方法提示