#1212. [HNOI2004]L语言
Online Judge：Bzoj-1212，Luogu-2292
Label：Trie，Dp
题目描述
大致题意：
给定一个含有n个单词的字典，现在一共有m个询问，每个询问输入一个字符串，问这个字符串能被理解的最长前缀位置p是多少，最长前缀从1~p构成的字符串必须能被字典中的单词分割。比如一个字典含有单词{"what"，"is"，“your”，“name”}，那么对于某询问"isyournamewty"的最长前缀长度为10。
输入格式
输入文件第一行是两个正整数n和m，表示字典D中有n个单词，且有m段文章需要被处理。 之后的n行每行描述一个单词，再之后的m行每行描述一段文章，所有字符都是小写字母。 其中(1<=n, m<=20)，每个单词长度不超过10，每段文章长度不超过(10^6)。
输出格式
对于输入的每一段文章，你需要输出这段文章在字典D可以被理解的最长前缀的位置。
样例
输入
4 3
is
name
what
your
whatisyourname
whatisyouname
whaisyourname
输出
14
6
0
样例解释
询问1：整段文章’whatisyourname’都能被理解
询问2：前缀’whatis’能够被理解
询问3：没有任何前缀能够被理解
题解：
由于文章长度的数据范围达1e6，对于这种大数据的查询考虑使用Trie。
先套Trie模板，把字典中的单词插入Trie中。然后就是对于每个询问的查询操作了。我们发现询问的字符串的长度很大，而且可能的组成方案不止一种，于是一开始决定对于每种方案进行记忆化搜索，然后xjb递归，结果貌似复杂度没问题但是由于常数巨大我也不知道为什么TLE了？？
其实不用递归来递归去。。用一个bool数组来转移状态就可以了。
定义(ok[i])表示询问的字符串中前i个字符构成的字符串能否由字典中的单词组成。
那么将普通的Trie查找改一下，如果当前节点是某单词的结尾，那么就把当前遍历到的位置标记ok=1。单词询问的最多运行次数大约为(O(1e6*10))。
代码如下，详见注释↘
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m;
int f[1010][27],tot;
bool ok[N],is[1010];
void insert(char *s){
int p=0;
for(int i=0;i<strlen(s);++i){
int x=s[i]-'a';
if(!f[p][x])f[p][x]=++tot;
p=f[p][x];
}
is[p]=1;//标记是某单词结尾的节点
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
char s[12];scanf("%s",s);
insert(s);
}
while(m--){
char s[N];scanf("%s",s+1);
int len=strlen(s+1),ans=0;
memset(ok,0,sizeof(ok));
ok[0]=1;//关于ok数组的定义见上面
for(int i=0;i<=len;i++){
if(!ok[i])continue;
ans=i;
for(int j=i+1,p=0;j<=len;j++){
int x=s[j]-'a';
p=f[p][x];
if(!p)break;
if(is[p])ok[j]=1;//可以拼到j这个位置
}
}
printf("%d
",ans);
}
}