题目描述
标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。
一段文章T是由若干小写字母构成。一个单词W也是由若干小写字母构成。一个字典D是若干个单词的集合。我们称一段文章T在某个字典D下是可以被理解的，是指如果文章T可以被分成若干部分，且每一个部分都是字典D中的单词。
例如字典D中包括单词{‘is’, ‘name’, ‘what’, ‘your’}，则文章‘whatisyourname’是在字典D下可以被理解的，因为它可以分成4个单词：‘what’, ‘is’, ‘your’, ‘name’，且每个单词都属于字典D，而文章‘whatisyouname’在字典D下不能被理解，但可以在字典D’=D+{‘you’}下被理解。这段文章的一个前缀‘whatis’，也可以在字典D下被理解，而且是在字典D下能够被理解的最长的前缀。
给定一个字典D，你的程序需要判断若干段文章在字典D下是否能够被理解。并给出其在字典D下能够被理解的最长前缀的位置。
输入输出格式
输入格式：
输入文件第一行是两个正整数n和m，表示字典D中有n个单词，且有m段文章需要被处理。之后的n行每行描述一个单词，再之后的m行每行描述一段文章。
其中1<=n, m<=20，每个单词长度不超过10，每段文章长度不超过1M。
输出格式：
对于输入的每一段文章，你需要输出这段文章在字典D可以被理解的最长前缀的位置。
输入输出样例
输入样例#1：
4 3
is
name
what
your
whatisyourname
whatisyouname
whaisyourname
输出样例#1：
14 （整段文章’whatisyourname’都能被理解）
6 （前缀’whatis’能够被理解）
0 （没有任何前缀能够被理解）
题解
为什么AC自动机没什么近乎模板的题写啊QAQ
在上古年代写过一个Trie+爆搜的代码↓
/*
qwerta
P2292 [HNOI2004]L语言
Accepted
100
代码 C++，1.01KB
提交时间 2018-05-19 16:28:10
耗时/内存
832ms, 6812KB
*/
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct emm{
int z[];
bool en;
}a[];
char s[];
int f[];
int t=;
void build()
{
int d=strlen(s)-;
int e=;
while(d>=)
{
if(a[e].z[s[d]-])e=a[e].z[s[d]-];
else e=a[e].z[s[d]-]=++t;
d--;
}
a[e].en=true;
return;
}
int ans=;
void search(int c)
{
int e=,d=c-;
while(d>=&&a[e].z[s[d]-])
{
//cout<<c<<" ";
e=a[e].z[s[d]-];
if(a[e].en)
{
if(f[d]||d==)
{f[c]=;ans=c;return;}
}
d--;
}
return;
}
int main()
{
//freopen("a.in","r",stdin);
int n,m;
cin>>n>>m;
for(int i=;i<=n;++i)
{
cin>>s;
build();
}
for(int i=;i<=m;++i)
{
ans=;
cin>>s;
int len=strlen(s);
memset(f,,sizeof(f));
f[]=;
for(int j=;j<=len;++j)
search(j);
cout<<ans<<endl;
}
return ;
}
感觉自己现在写不出这种上古绝学了QAQ（逃
居然比上古绝学慢了三百毫秒ＱＡＱ
/*
qwerta
P2292 [HNOI2004]L语言
Accepted
100
代码 C++，2.53KB
提交时间 2018-10-08 08:42:03
耗时/内存
1121ms, 28908KB
*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
#define R register
struct emm{
int fal;
int nxt[];
int tag,l;
}AC[];//Tree结构体
queue<int>q;
struct ahh{
int f,e;
}a[];//用来区间覆盖
int h[];
bool sf[];//判重
int main()
{
//freopen("a.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(false),cout.tie(false);//关闭同步流（卡常
int n,m;
cin>>n>>m;
int cnt=;
//build_Trie
for(R int i=;i<=n;++i)
{
string s;
cin>>s;
int len=s.length();
int now=;
for(R int j=;j<len;++j)
{
if(!AC[now].nxt[s[j]-'a'])
AC[now].nxt[s[j]-'a']=++cnt;
now=AC[now].nxt[s[j]-'a'];
}
AC[now].tag=i;
AC[now].l=len;//记录这个区间的长度
}
//get_fail
{
for(R int i=;i<;++i)
if(AC[].nxt[i])
{
AC[AC[].nxt[i]].fal=;
q.push(AC[].nxt[i]);
}
while(!q.empty())
{
int x=q.front();q.pop();
for(R int i=;i<;++i)
{
if(AC[x].nxt[i])
{
AC[AC[x].nxt[i]].fal=AC[AC[x].fal].nxt[i];
q.push(AC[x].nxt[i]);
}
else
AC[x].nxt[i]=AC[AC[x].fal].nxt[i];
}
}
}
//runAC
for(R int i=;i<=m;++i)
{
//cout<<"i="<<i<<endl;
memset(a,,sizeof(a));
memset(h,,sizeof(h));
int tot=;
string t;
cin>>t;
int lent=t.length();
int now=;
for(R int j=;j<lent;++j)
{
now=AC[now].nxt[t[j]-'a'];
for(R int k=now;k;k=AC[k].fal)
if(AC[k].tag)
{
//a[++tot].r=j;
//a[tot].l=j-AC[k].l+1;
int ll=j-AC[k].l+;//这个区间的左端点＝右端点－长度＋１
a[++tot].f=h[ll];//邻接链表加边
h[ll]=tot;
a[tot].e=j;
}
}
//cout<<"get"<<endl;
//bfs
memset(sf,,sizeof(sf));
int ans=-;
{
q.push();
while(!q.empty())
{
int x=q.front();q.pop();
//cout<<"x="<<x<<endl;
ans=max(ans,x-);
for(R int i=h[x];i;i=a[i].f)
if(!sf[a[i].e])//判重
{
sf[a[i].e]=;
q.push(a[i].e+);
//cout<<"push "<<a[i].e+1<<endl;
}
}
}
cout<<ans+<<endl;
}
return ;
}