做一的同志小说网站,汉服网站设计模板,自己做网站内容读取太慢,动态视频网站开发文章目录题目描述解析代码题目描述 解析
做的不错 把trie树真的当成一棵树递归即可 注意一个标记时的问题#xff1a;
void AC(){int lstrlen(s01),pl1;for(int i1;il;i){int aask(s0[i]);pltr[pl][a];int kpl;while(k1){if(ok[k]) break;//注意#xff01;ok[k]1;…
文章目录题目描述解析代码题目描述 解析
做的不错 把trie树真的当成一棵树递归即可 注意一个标记时的问题
void AC(){int lstrlen(s01),pl1;for(int i1;il;i){int aask(s0[i]);pltr[pl][a];int kpl;while(k1){if(ok[k]) break;//注意ok[k]1;knxt[k];}}
}原题数据不写这行没关系 但我觉得好像有点问题啊。。。 首先正确性是可以保证的 要是不加可能不断重复标记感觉也许会卡成100n 加上后也快了一倍
也强调一下这个标记往回找不漏的问题第一交又忘了qwq
代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int N3e6100;
const int M1e7100;
int tr[N][5],tot1;
int n,l;
char s[N],s0[M];
int cnt0;
int id[N];
int ok[N];
int dep[N],fa[N];
int ask(char c){if(cE) return 1;else if(cS) return 2;else if(cW) return 3;else return 4;
}
void build(int k){int lstrlen(s1),pl1;for(int i1;il;i){int aask(s[i]);if(!tr[pl][a]){tr[pl][a]tot;dep[tot]dep[pl]1;fa[tot]pl;}pltr[pl][a];}id[k]pl;//num[pl];
}
int q[N],st,ed,nxt[N];
void bfs(){stedq[1]1;for(int i1;i4;i) tr[0][i]1;nxt[1]0;while(sted){int nowq[st];for(int i1;i4;i){if(!tr[now][i]) tr[now][i]tr[nxt[now]][i];else{q[ed]tr[now][i];nxt[tr[now][i]]tr[nxt[now]][i];}}}return;
}
void AC(){int lstrlen(s01),pl1;for(int i1;il;i){int aask(s0[i]);pltr[pl][a];int kpl;while(k1){if(ok[k]) break;ok[k]1;knxt[k];}}
}
int find(int pl){//printf(pl%d\n,pl);if(pl1) return 0;if(ok[pl]) return dep[pl];return find(fa[pl]);
}
int main() {scanf(%d%d,l,n);scanf(%s,s01);for(int i1;in;i) scanf(%s,s1),build(i);bfs();AC();for(int i1;in;i){printf(%d\n,find(id[i]));}return 0;
}/*
11 5
EESSWNNSWSE
W
EEN
SSESSW
SSWSSE
SWS
*/
