正題

評(píng)測(cè)記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P2922

---

題目大意

給n個(gè)01串，用m個(gè)01串匹配，如果n是m的前綴或者m是n的前綴那么就算匹配成功，求每個(gè)串有多少個(gè)匹配成功。

---

解題思路

我們可以用Trie樹(shù)，分為0和1分支，然后在路上統(tǒng)計(jì)下面有多少個(gè)匹配。

---

code

#include<cstdio> using namespace std; int n,m,nn,end[500001],l[500001][2],x,tot,sum[500001]; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&nn);int now=0;for(int i=1;i<=nn;i++){scanf("%d",&x);if(!l[now][x]) l[now][x]=++tot;//新建節(jié)點(diǎn)now=l[now][x];//下一個(gè)點(diǎn)sum[now]++;//路上統(tǒng)計(jì)}end[now]++;//結(jié)束統(tǒng)計(jì)}for(int i=1;i<=m;i++){scanf("%d",&nn);int now=0,ans=0,j;bool flag=false;for(j=1;j<=nn;j++){scanf("%d",&x);if(!l[now][x]||flag) {flag=true;continue;}//不再匹配now=l[now][x];//下一個(gè)點(diǎn)ans+=end[now];//統(tǒng)計(jì)答案}if(!flag)ans+=sum[now]-end[now];//特判printf("%d\n",ans);} }

總結(jié)

以上是生活随笔為你收集整理的P2922-[USACO08DEC]秘密消息Secret Message【Trie,字符串】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。