bzoj1212——L语言
1、题目大意:每一个字符串都可以分解成一些个单词组成,现在给你一些单词,再给你一个字符串,
问从字符串头开始,最长可以分解成单词多长呢
2、分析:dp吧,设f[i]为从0开始,到i结束的字符串前缀是否可以被分解,因为单词长度很小,所以,这就T了,
(什么逻辑),怎么才能不T呢,我们在转移的时候用Trie,可以把转移从O(100)优化成O(10),那么这就AC了
3、代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct Trie{
int ch[1000][50];
int val[1000];
int len;
char s[100];
char str[1000010];
int f[1000210];
int size;
inline int num(char x){
return x - 'a';
}
inline void insert(){
int u = 0;
for(int i = 0; i < len; i ++){
int c = num(s[i]);
if(!ch[u][c]){
ch[u][c] = ++ size;
}
u = ch[u][c];
}
val[u] = 1;
}
inline void find(int e){
int u = 0;
for(int i = 1; i <= len; i ++){
int c = num(s[i]);
if(!ch[u][c]) return;
u = ch[u][c];
if(val[u]) f[e + i] = 1;
}
return;
}
inline int dp(int l){
f[0] = 1;
for(int i = 1; i <= 10; i ++) f[i] = 0;
int gh = 0;
for(int i = 0; i <= l; i ++){
f[i + 10] = 0;
if(!f[i]) continue;
if(i > gh) gh = i;
for(int j = i; j <= min(i + 9, l - 1); j ++){
s[j - i + 1] = str[j];
}
len = min(i + 9, l - 1) - i + 1;
find(i);
}
return gh;
}
} wt;
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++){
scanf("%s", wt.s);
wt.len = strlen(wt.s);
wt.insert();
}
for(int i = 1; i <= m; i ++){
scanf("%s", wt.str);
int len = strlen(wt.str);
printf("%d\n", wt.dp(len));
}
return 0;
}