首先改正方式是将 ```insert```函数中更新 ```last``` 值提前到刚刚新建 ```cur``` 的时候,对于 ```last``` 的定义理解,其实不止是终止节点(即当前没有后继节点的点),也可以是最长的后缀从属于的类所映射出的点(即全串所在)。可以看眼我的[博客](https://www.luogu.com.cn/blog/wtfwflsnb/hou-zhui-zi-dong-ji-post)(推销捏),所以后续拆点处理时新建的 ```clone``` 点并不是真正的 ```last```
对于 ```AC#1``` 其实很好解释,因为 $1e6$ 个 $z$ 不会需要拆点啦~[在拆点条件中assert(0)](https://www.luogu.com.cn/record/127015296)
accode
```cpp
#include<bits/stdc++.h>
#define MAXN 3000005
#define MAXL 30
using namespace std;
inline void read(int &n){
int s=0,t=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') t=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<3)+(s<<1)+(c^48);c=getchar();
}
n=s*t;
}
inline void put(long long n){
if(n<0){
putchar('-');n=-n;
}
if(n<10){
putchar(n+48);return;
}
put(n/10);
putchar(n%10+48);
}
struct node{
int v,nxt;
}e[MAXN*2];
int last,cnt,tot,link[MAXN],head[MAXN],t[MAXN][MAXL];
long long ans,len[MAXN],siz[MAXN];
char s[MAXN];
inline void firstwork(){
link[0]=-1;siz[0]=1;
}
inline int exch(char ch){
return ch-'a'+1;
}
inline void insert(char ch)
{
int p=last,cur=++cnt,c=exch(ch);
len[cur]=len[last]+1;siz[cur]++;last=cnt;
while(p!=-1&&!t[p][c]){
t[p][c]=cur;p=link[p];
}
if(p==-1) link[cur]=0;
else{
int q=t[p][c];
if(len[p]+1==len[q]) link[cur]=q;
else{
int clone=++cnt;
len[clone]=len[p]+1;
link[clone]=link[q];
for(register int i=1;i<=26;++i) t[clone][i]=t[q][i];
while(p!=-1&&t[p][c]==q){
t[p][c]=clone;p=link[p];
}
link[cur]=link[q]=clone;
}
}
}
inline void add(int u,int v){
++tot;
e[tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
inline void dfs(int u){
for(register int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
dfs(v);siz[u]+=siz[v];
}
if(siz[u]!=1&&siz[u]*len[u]>ans) ans=siz[u]*len[u];
}
int main(){
//freopen("P3804_3.in","r",stdin);
//freopen("P3804_3.ans","w",stdout);
int len;
cin>>s;
len=strlen(s);
firstwork();
for(register int i=0;i<len;++i) insert(s[i]);
for(register int i=0;i<=cnt;++i) add(link[i],i);
dfs(0);put(ans);putchar('\n');
return 0;
}
```
by Mo20 @ 2023-10-02 11:49:06
@[Mo20](/user/448983)
对了,谢谢dalao
by WxjzKK @ 2023-10-02 12:36:23