社区讨论
萌新刚学OI,求助
P6139【模板】广义后缀自动机(广义 SAM)参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @loce6c55
- 此快照首次捕获于
- 2023/10/30 12:20 2 年前
- 此快照最后确认于
- 2023/11/05 00:00 2 年前
5分WA
CPP#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#define N 4000017
#define ll long long
using namespace std;
char s[N];
int ch[N][26],fa[N],len[N],lst,num;
bool vis[N];
ll siz[N];
void build_trie()
{
int n = strlen(s + 1);
int u = 1;
for(int i = 1;i <= n;i += 1)
{
int x = s[i] - 'a';
if(!ch[u][x])ch[u][x] = ++num;
u = ch[u][x];
}
}
void Extend(int p,int c)
{
len[p] = len[lst] + 1;
int f = fa[lst];
while(f && !ch[f][c]){
ch[f][c] = p;
f = fa[f];
}
if(!f){
fa[p] = 1;
return;
}
int x = ch[f][c];
if(len[f] + 1 == len[x])
{
fa[p] = x;
return;
}
int y = ++num;
len[y] = len[f] + 1;
fa[y] = fa[x];
fa[p] = fa[x] = y;
memcpy(ch[y],ch[x],sizeof(ch[y]));
while(f && ch[f][c] == x)ch[f][c] = y,f = fa[f];
}
void bfs()
{
queue<pair<int,int> >q;
int u = 1;
for(int i = 0;i < 26;i += 1)
if(ch[u][i])q.push(make_pair(u,i));
while(!q.empty())
{
int x = q.front().second;
lst = q.front().first;
u = ch[lst][x];
q.pop();
Extend(u,x);
for(int i = 0;i < 26;i += 1)
if(ch[u][i])q.push(make_pair(u,i));
}
}
void dfs(int u)
{
if(vis[u])return;
vis[u] = 1;
for(int i = 0;i < 26;i += 1)
{
int v = ch[u][i];
if(!v)continue;
dfs(v);
siz[u] += siz[v];
}
}
int main()
{
lst = num = 1;
int m;
scanf("%d",&m);
for(int i = 1;i <= m;i += 1)
{
scanf("%s",s + 1);
build_trie();
}
bfs();
for(int i = 2;i <= num;i += 1)
siz[i] = 1;
dfs(1);
printf("%lld\n",siz[1]);
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...