均摊 $\mathcal{O}(n)$，因为每次向下最多一层。我很好奇你是怎么预处理的。
by sqrtDataStructure @ 2023-11-27 18:22:21
好吧上面我在狗叫，均摊 $\mathcal{O}(n)$ 的主要原因是每次向上跳都会导致匹配长度至少 $-1$，而匹配长度总共为 $n$。
by sqrtDataStructure @ 2023-11-27 18:23:22
@[sqrtDataStructure](/user/484006) 就继承link祖先上的转移边
```cpp
unordered_map<int, int> mp;
int hash(int x, int y){
return x * 1333 + y;
}
void rebuild(){
buildTree();
int cnt = 0;
auto dfs = [this, &cnt] (auto self, int x) -> void {
for(int i = 0; i < Sizeset; i ++){
int to = tr[x].ch[i];
if(! to) {
tr[x].ch[i] = tr[tr[x].link].ch[i];
if(tr[x].ch[i]){
if(mp.count(hash(tr[x].link, i))){
mp[hash(x, i)] = mp[hash(tr[x].link, i)];
}
else{
mp[hash(x, i)] = tr[tr[x].link].maxlen;
}
}
}
}
for(auto to : link_tree[x]){
self(self, to);
}
};
dfs(dfs, 1);
}
void slove(string &s, int n){
rebuild();
int x = 1, ans = 0, cnt = 0;
for(int i = 0; i < n; i ++){
int v = s[i] - Minset;
if(tr[x].ch[v]){
if(mp.count(hash(x, v))){
cnt = mp[hash(x, v)];
}
x = tr[x].ch[v];
cnt += 1;
ans = max(ans, cnt);
}
else{
x = 1;
cnt = 0;
}
}
cout << ans << '\n';
}
```
by WCPWCPWCP @ 2023-11-27 19:02:29
@[WCPWCPWCP](/user/640499) 因为 LCS 长度你一次最多增加 1，减少最多减少到 0，所以你最多跳 n 次 link。
by DaydreamWarrior @ 2024-02-08 16:16:30