LuoguP2292 L语言

题目描述

令f[i]表示文章的1～i是否能够由单词构成，那么f[i]=f[j]&&OK_j+1,i。

其中OK_j+1,i表示j+1到i能够由单词构成。

显然不能直接转移，考虑怎样快速算出OK来.

我们注意到每个单词不超过20，且数量不超过10，那么我们可以建一颗Trie树，插入这些单词。

然后顺序枚举每一位，如果某一位i可行，那么考虑它对后面位的影响（即刷表法）。

因为树的深度最多为10，每次最坏O（10）的检索，总复杂度O（20*10*1e6），但是还是很快。

 

#include<bits/stdc++.h> #define RG register #define IL inline #define LL long long using namespace std;IL int gi() {RG int x=0,w=0; char ch=0;while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return w?-x:x; }const int N=30; const int M=1100000;char str[21],s[M]; int n,m,L,num,f[M],tr[210][27],End[210];IL void Insert(char *s) {int i,p=0,now,len=strlen(s);for (i=0;i<len;++i) {now=s[i]-'a'+1;if (!tr[p][now]) tr[p][now]=++num;p=tr[p][now];}End[p]=1; }int main () {RG int i,j,p;n=gi(),m=gi();for (i=1;i<=n;++i)scanf("%s",str),Insert(str);while (m--) {scanf("%s",s+1),L=strlen(s+1);memset(f,0,sizeof(f)); for (i=0,f[0]=1;i<=L;++i) {if (!f[i]) continue;j=i+1,p=tr[0][s[j]-'a'+1];while (j<=L&&p) {if (End[p]) f[j]=1;p=tr[p][s[++j]-'a'+1];}}for (i=L;i>=0;--i)if (f[i]) {printf("%d\n",i);break;}}return 0; } BY BHLLX

 

转载于:https://www.cnblogs.com/Bhllx/p/10334336.html

总结

以上是生活随笔为你收集整理的LuoguP2292 L语言的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。