題目大意：給定一個單詞表和m個字符串 問每個字符串的最長的前綴，滿足這個前綴可以拆分成一些字符串 使這些字符串都在單詞表中出現過
再也不敢看錯數據范圍了……一道明明用Trie樹能解決的問題居然被我寫了AC自動機……
將單詞表中的單詞全都插入AC自動機 每個單詞所在的節點記錄這個單詞的長度
然後對於每個字符串 用f[i]表示長度為i的前綴是否能拆分成單詞表中的單詞 跑AC自動機
對於每個匹配的節點 從這個節點開始到根的fail路徑上的所有len f[i]|=f[i-len]
找到最大的為1的f[i]即是答案
由於單詞長度最大為10 所以直接用Trie樹暴力即可
#include#include #include #include #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<
