BZOJ 1212 HNOI 2004 L语言 Trie树

标题效果:给一些词。和几个句子,当且仅当句子可以切子可以翻译词典,这意味着该子将被翻译。

找到最长前缀长度可以被翻译。

思维:使用Trie树阵刷。你可以刷到最长的地方是最长的字符串可以翻译到的地方。

PS:在BZOJ上Trie竟然比AC自己主动机快。我的渣代码都刷到第一篇了。。

CODE:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; struct Trie{
Trie *son[27];
bool end; Trie() {
memset(son,NULL,sizeof(son));
end = false;
}
}*root = new Trie(); int words,cnt;
char s[1 << 20|100],temp[20];
bool f[1 << 20|100]; inline void Insert(char *s)
{
Trie *now = root;
while(*s != '\0') {
if(now->son[*s - 'a'] == NULL)
now->son[*s - 'a'] = new Trie();
now = now->son[*s - 'a'];
++s;
}
now->end = true;
} inline void Ask(char *s,int i)
{
Trie *now = root;
int t = 0;
while(*s != '\0') {
if(now->son[*s - 'a'] == NULL)
return ;
now = now->son[*s - 'a'];
++s;
++t;
if(now->end) f[i + t] = true;
}
if(now->end) f[i + t] = true;
} inline int Work()
{
memset(f,false,sizeof(f));
f[0] = true;
int re = 0,length = strlen(s + 1);
for(int i = 0; i <= length; ++i) {
if(!f[i]) continue;
re = i;
Ask(s + i + 1,i);
}
return re;
} int main()
{
cin >> words >> cnt;
for(int i = 1; i <= words; ++i) {
scanf("%s",temp);
Insert(temp);
}
for(int i = 1; i <= cnt; ++i) {
scanf("%s",s + 1);
printf("%d\n",Work());
}
return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

上一篇:硅谷新闻2--禁止viewpager预加载


下一篇:Java自定义注解及使用