在下面这份代码中的 add 函数,表示使用链式前向星的加边操作,但是两种写法一种 WA 73pts,另一种 AC。求解释。
void add(int x,int y){//WA
e[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}
void add(int x,int y){//AC
idx++
e[idx] = y;
ne[idx] = h[x];
h[x] = idx;
}
完整代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e6+10;
struct sam{
int father,len,son[30];
}Trie[N];
char a[N];
int siz = 1,last = 1;
int ne[N],h[N],e[N],idx;
ll cnt[N],ans;
void add(int x,int y){
idx++;
e[idx] = y;
ne[idx] = h[x];
h[x] = idx;
}
void Newnode(int len){
siz++;
Trie[siz].len = len;
Trie[siz].father = 0;
memset(Trie[siz].son,0,sizeof(Trie[siz].son));
}
void Insert(int c){
Newnode(Trie[last].len+1);
int p = last,now = siz;
cnt[siz] = 1;
while(p != 0 && !Trie[p].son[c])
Trie[p].son[c] = now,p = Trie[p].father;
if(p == 0) Trie[now].father = 1;
else{
int q = Trie[p].son[c];
if(Trie[p].len+1 == Trie[q].len)
Trie[now].father = q;
else{
Newnode(Trie[p].len+1);
int cop = siz;
memcpy(Trie[cop].son,Trie[q].son,sizeof(Trie[cop].son));
Trie[cop].father = Trie[q].father;
Trie[now].father = Trie[q].father = cop;
while(p != 0 && Trie[p].son[c] == q)
Trie[p].son[c] = cop,p = Trie[p].father;
}
}
last = now;
}
void dfs(int u){
for(int i = h[u];i;i = ne[i]){
dfs(e[i]);
cnt[u] += cnt[e[i]];
}
if(cnt[u] != 1) ans = max(ans,1ll*cnt[u]*Trie[u].len);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>a; //Newnode(1);
int alen = strlen(a);
for(int i = 0;i<alen;i++)
Insert(a[i] - 'a');
for(int i = 2;i<=siz;i++)
add(Trie[i].father,i);
dfs(1);
cout<<ans<<endl;
return 0;
}