已AC但有疑问 & 警示后人
查看原帖
已AC但有疑问 & 警示后人
808222
Kotobuki_Tsumugi楼主2024/5/3 18:18

在下面这份代码中的 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;
}
2024/5/3 18:18
加载中...