社区讨论

求助,错误代码AC

P3804【模板】后缀自动机(SAM)参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo2ks2ax
此快照首次捕获于
2023/10/23 15:27
2 年前
此快照最后确认于
2023/10/23 15:27
2 年前
查看原帖
RT,这是AC代码
CPP
#include <bits/stdc++.h>

#define ll long long
#define dub long double
const int MAXN = 2e6+7;
const int inf = 1e9+7;
const dub eps = 1e-14;

using namespace std;

int tr[MAXN][30], len[MAXN], fail[MAXN];
int lst = 1, cnt = 1;
string s;
queue <int> q;
int in[MAXN], f[MAXN];

inline int read( )<%
    int x = 0 ; short w = 0 ; char ch = 0;
    while( !isdigit(ch) ) { w|=ch=='-';ch=getchar();}
    while( isdigit(ch) ) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return w ? -x : x;
%>

int get(char x){ return x - 'a'; }

void insert(int x){
	int p = lst, np = ++cnt, q, nq; lst = np;
	len[np] = len[p] + 1; f[np] = 1;
	for(; p and !tr[p][x]; p = fail[p]) tr[p][x] = np;
	if(!p) fail[np] = 1;
	else if(len[q = tr[p][x]] == len[p] + 1) fail[np] = q;
	else{
		nq = ++cnt;
		fail[nq] = fail[q];
		len[nq] = len[p] + 1;
		fail[q] = fail[np] = nq;
		memcpy(tr[nq], tr[q], sizeof(tr[q]));
		for(;p and tr[p][x] == q; p = fail[p]) tr[p][x] = nq;
	}
}

void tpsort( ){
	for(int i = 1; i <= cnt; i++)
		in[fail[i]]++;
	for(int i = 1; i <= cnt; i++)
		if(!in[i]) q.push(i);
	while(!q.empty()){
		int x = q.front( ); q.pop( );
		f[fail[x]] += f[x];
		in[fail[x]]--;
		if(!in[fail[x]]) q.push(fail[x]);
	}
}

int main( )<%
	
	cin >> s;
	
	for(int i = 0; i < (int)s.size( ); i++)
		insert(get(s[i]));
	
	tpsort();
	
	ll ans = 0;	
	for(int i = 2; i <= cnt; i++)
		if(f[i] > 1) ans = max(ans, (ll)f[i] * len[i]);
	
	cout << ans;
	
	return 0;
%>
我把else if(len[q = tr[p][x]] == len[p] + 1) 改成了else if(len[q = tr[p][x]] == len[np]) 过了,求解。

回复

1 条回复,欢迎继续交流。

正在加载回复...