傳送門(mén)：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1212

思路：這題AC自動(dòng)機(jī)都不用建，只要trie就好了。。。

首先令f[i]表示到i的前綴能否被理解，那么答案就是f[i]==1時(shí)最大的i

轉(zhuǎn)移也很簡(jiǎn)單，如果f[i]==1，這個(gè)串就可以從i+1開(kāi)始匹配一個(gè)新單詞，因?yàn)閱卧~長(zhǎng)度<=10，暴力在trie上走就是了

設(shè)trie上匹配到一個(gè)長(zhǎng)度為j的單詞,那么f[i+j]=1。

#include<cstdio> #include<cstring> #include<algorithm> const int maxn=(1<<20)+10; using namespace std; int n,m,len,f[maxn];char s[maxn];;struct trie{int tot,ch[2010][26];bool ok[maxn];void insert(){int p=0,len=strlen(s);for (int i=0;i<len;p=ch[p][s[i]-'a'],i++) if (!ch[p][s[i]-'a']) ch[p][s[i]-'a']=++tot;ok[p]=1;} }T;int work(int t){int ans=0;len=strlen(s+1);f[0]=t;for (int i=0;i<=len;i++){if (f[i]!=t) continue;else ans=i;for (int p=0,j=i+1;j<=len;j++){p=T.ch[p][s[j]-'a'];if (!p) break;if (T.ok[p]) f[j]=t;}}return ans; }int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%s",s),T.insert();for (int i=1;i<=m;i++) scanf("%s",s+1),printf("%d\n",work(i));return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/thythy/p/5493562.html

總結(jié)

以上是生活随笔為你收集整理的bzoj1212: [HNOI2004]L语言的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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