文章目錄

• 題目描述
• 解析
• 代碼

題目描述

解析

做的不錯
把trie樹真的當成一棵樹遞歸即可
注意一個標記時的問題：

void AC(){int l=strlen(s0+1),pl=1;for(int i=1;i<=l;i++){int a=ask(s0[i]);pl=tr[pl][a];int k=pl;while(k>1){if(ok[k]) break;//注意！ok[k]=1;k=nxt[k];}} }

原題數據不寫這行沒關系
但我覺得好像有點問題啊。。。
首先正確性是可以保證的；
要是不加，可能不斷重復標記，感覺也許會卡成100n
加上后也快了一倍

也強調一下這個標記往回找不漏的問題，第一交又忘了qwq

代碼

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=3e6+100; const int M=1e7+100; int tr[N][5],tot=1; int n,l; char s[N],s0[M]; int cnt=0; int id[N]; int ok[N]; int dep[N],fa[N]; int ask(char c){if(c=='E') return 1;else if(c=='S') return 2;else if(c=='W') return 3;else return 4; } void build(int k){int l=strlen(s+1),pl=1;for(int i=1;i<=l;i++){int a=ask(s[i]);if(!tr[pl][a]){tr[pl][a]=++tot;dep[tot]=dep[pl]+1;fa[tot]=pl;}pl=tr[pl][a];}id[k]=pl;//num[pl]++; } int q[N],st,ed,nxt[N]; void bfs(){st=ed=q[1]=1;for(int i=1;i<=4;i++) tr[0][i]=1;nxt[1]=0;while(st<=ed){int now=q[st++];for(int i=1;i<=4;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 l=strlen(s0+1),pl=1;for(int i=1;i<=l;i++){int a=ask(s0[i]);pl=tr[pl][a];int k=pl;while(k>1){if(ok[k]) break;ok[k]=1;k=nxt[k];}} } int find(int pl){//printf("pl=%d\n",pl);if(pl==1) return 0;if(ok[pl]) return dep[pl];return find(fa[pl]); } int main() {scanf("%d%d",&l,&n);scanf("%s",s0+1);for(int i=1;i<=n;i++) scanf("%s",s+1),build(i);bfs();AC();for(int i=1;i<=n;i++){printf("%d\n",find(id[i]));}return 0; }/* 11 5 EESSWNNSWSE W EEN SSESSW SSWSSE SWS */

總結

以上是生活随笔為你收集整理的YBTOJ：前缀匹配（AC自动机）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。