大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
标题效果:给定词的列表,并m串 每个字符串q个最长前缀,这个前缀可满足拆分成一些字符串 这些字符串中存在的词汇太
再也不怕错误的数据范围……有一个很明显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; } }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117266.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...