F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 4327 >> 请问是哪里超空间了????自己算没问题啊
Stupider @ 2018-07-27 09:20:32
[ Quote ] [ Edit ] [ Delete ] 1#
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1e7+1,maxa=1e5+10;
char ch[maxn][4];
char a[maxa],s[maxn];
int cnt=1,nxt[maxn];
vector<int>v;
queue<int>Q;
bool book[maxn];
int re(char a){
if(a=='E')return 0;
else if(a=='S')return 1;
else if(a=='W')return 2;
else return 3;
}
void make(char *a){
int len=strlen(a),u=1;
for(int i=0;i<len;++i){
int t=re(a[i]);
if(!ch[u][t]){
ch[u][t]=++cnt;
}
u=ch[u][t];
}
v.push_back(u);
return ;
}
void bfs(){
Q.push(1);
nxt[1]=0;
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=0;i<=3;++i)
if(!ch[u][i]){
ch[u][i]=ch[nxt[u]][i];
}
else{
Q.push(ch[u][i]);
nxt[ch[u][i]]=ch[nxt[u]][i];
}
}
}
void find(char *s){
int len=strlen(s),u=1;
for(int i=0;i<len;++i){
int t=re(s[i]);
u=ch[u][t];
int k=u;
while(!book[k]&&k>1){
book[k]=1;
k=nxt[k];
}
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
scanf("%s",s);
for(int i=0;i<=3;++i)ch[0][i]=1;
for(int i=1;i<=m;++i){
scanf("%s",a);
make(a);
}
bfs();
while(!Q.empty())Q.pop();
find(s);
memset(nxt,0,sizeof(nxt));
Q.push(1);
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=0;i<=3;++i){
nxt[ch[u][i]]=nxt[u]+book[ch[u][i]];
if(ch[u][i]>u){
Q.push(ch[u][i]);
}
}
}
int len=v.size();
for(int i=0;i<len;++i){
cout<<nxt[v[i]]<<endl;
}
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back