首页 > 代码库 > BZOJ 1212 HNOI2004 L语言 AC自动机(Trie树)+动态规划
BZOJ 1212 HNOI2004 L语言 AC自动机(Trie树)+动态规划
题目大意:给定一个单词表和m个字符串 问每个字符串的最长的前缀,满足这个前缀可以拆分成一些字符串 使这些字符串都在单词表中出现过
再也不敢看错数据范围了……一道明明用Trie树能解决的问题居然被我写了AC自动机……
将单词表中的单词全都插入AC自动机 每个单词所在的节点记录这个单词的长度
然后对于每个字符串 用f[i]表示长度为i的前缀是否能拆分成单词表中的单词 跑AC自动机
对于每个匹配的节点 从这个节点开始到根的fail路径上的所有len f[i]|=f[i-len]
找到最大的为1的f[i]即是答案
由于单词长度最大为10 所以直接用Trie树暴力即可
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 1050000 using namespace std; struct Trie{ int len; Trie *fail,*son[26]; void* operator new (size_t size); }*root,*mempool,*C; int n,m; char s[M]; void* Trie :: operator new (size_t size) { if(C==mempool) { C=new Trie[1<<15]; mempool=C+(1<<15); memset(C,0,sizeof(Trie)*(1<<15) ); } return C++; } void Insert(Trie*&p,char *pos,int dpt) { if(!p) p=new Trie; if(!*pos) { p->len=dpt; return ; } Insert(p->son[(*pos)-'a'],pos+1,dpt+1); } void BFS() { static Trie* q[1<<16]; static unsigned short r,h; int i;Trie *temp; for(i=0;i<26;i++) if(temp=root->son[i]) { temp->fail=root; q[++r]=temp; } while(r!=h) { Trie *p=q[++h]; for(i=0;i<26;i++) if(p->son[i]) { temp=p->fail; while( temp!=root && !temp->son[i] ) temp=temp->fail; if( temp->son[i] ) temp=temp->son[i]; p->son[i]->fail=temp; q[++r]=p->son[i]; } } } int Aho_Corasick_Automaton() { int i,re=0; Trie *p=root,*temp; static bool f[M];f[0]=1; for(i=1;s[i];i++) { f[i]=0; while( p!=root && !p->son[s[i]-'a'] ) p=p->fail; if(p->son[s[i]-'a']) { p=p->son[s[i]-'a']; for(temp=p;temp!=root;temp=temp->fail) if(temp->len) { f[i]|=f[i-temp->len]; if(f[i]) break; } } if(f[i]) re=i; } return re; } int main() { int i; cin>>n>>m; for(i=1;i<=n;i++) scanf("%s",s+1),Insert(root,s+1,0); BFS(); for(i=1;i<=m;i++) { scanf("%s",s+1); cout<<Aho_Corasick_Automaton()<<endl; } }
BZOJ 1212 HNOI2004 L语言 AC自动机(Trie树)+动态规划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。