社区讨论
求助,错误代码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 条回复,欢迎继续交流。
正在加载回复...