Description
标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。 一段文章T是由若干小写字母构成。一个单词W也是由若干小写字母构成。一个字典D是若干个单词的集合。 我们称一段文章T在某个字典D下是可以被理解的，是指如果文章T可以被分成若干部分，且每一个部分都是字典D中的单词。 例如字典D中包括单词{‘is’, ‘name’, ‘what’, ‘your’}，则文章‘whatisyourname’是在字典D下可以被理解的 因为它可以分成4个单词：‘what’, ‘is’, ‘your’, ‘name’，且每个单词都属于字典D，而文章‘whatisyouname’ 在字典D下不能被理解，但可以在字典D’=D+{‘you’}下被理解。这段文章的一个前缀‘whatis’，也可以在字典D下被理解 而且是在字典D下能够被理解的最长的前缀。 给定一个字典D，你的程序需要判断若干段文章在字典D下是否能够被理解。 并给出其在字典D下能够被理解的最长前缀的位置。
Solution
其实这个数据范围建一颗trie树就够了，但我还是建了AC自动机
建的时候每个节点记录一下长度
把字符串放在AC自动机上跑，f[i]=1表示文章的前缀i可以被理解，dp一下if(trie[t].cnt&&f[i-trie[t].len+1])f[i+1]=1;
#include#include #include #include #include #define MAXN 2000005using namespace std;struct Node{ int next[26],fail,cnt,len;}trie[305];int n,m,sz,root;int f[MAXN];char s[15],k[MAXN];int newnode(){ sz++; trie[sz].fail=trie[sz].cnt=trie[sz].len=0; memset(trie[sz].next,0,sizeof(trie[sz].next)); return sz;}void insert(char *word){ int p=root,i=0; while(word[i]) { int idx=word[i]-'a'; if(!trie[p].next[idx]) { trie[p].next[idx]=newnode(); trie[trie[p].next[idx]].len=trie[p].len+1; } p=trie[p].next[idx]; i++; } trie[p].cnt++;}queue q;void build(){ q.push(root); while(!q.empty()) { int p=q.front();q.pop(); for(int i=0;i<26;i++) { int t=trie[p].fail; while(t&&!trie[t].next[i])t=trie[t].fail; if(trie[p].next[i]) { trie[trie[p].next[i]].fail=t?trie[t].next[i]:root; q.push(trie[p].next[i]); } else trie[p].next[i]=t?trie[t].next[i]:root; } }}void work(){ memset(f,0,sizeof(f)); scanf("%s",k); int i=0,p=root; f[0]=1; while(k[i]) { int idx=k[i]-'a'; p=trie[p].next[idx]; int t=p; while(t) { if(trie[t].cnt&&f[i-trie[t].len+1])f[i+1]=1; t=trie[t].fail; } i++; } int ans=0; for(int j=1;j<=i;j++) if(f[j])ans=j; printf("%d\n",ans);}int main(){ scanf("%d%d",&n,&m); sz=0,root=newnode(); for(int i=1;i<=n;i++) { scanf("%s",s); insert(s); } build(); for(int i=1;i<=m;i++) work(); return 0;}