Trie+论快读的重要性
加了快读TLE --> <=200ms
事实证明对于这种大量读入字符的题我们要手！写！快！读！（getchar大法好）
（然而正解是Trie+dp/AC自动机）
好了，进入正题
我们用Trie把字典存起来，然后对于所给的串，在Trie上跑dfs即可
当然，dfs可以用记忆化搜索（然而优化效果不够）
#include<iostream> #include<cstdio> #include<cstring> using namespace std; inline int max(int &a,int &b) {return a>b ?a:b;} struct data{ int nxt[27]; bool end; }a[205]; int ans,n,m,cnt,len; char q[5000001]; bool vis[5000001]; inline void read_q(){ //手写快读 char c=getchar(); len=0; //len实时计算就不用每次清空原串 while(c<'a'||c>'z') c=getchar(); while('a'<=c&&c<='z') q[len++]=c,c=getchar(); } inline void insert(){ //建树 read_q(); int u=0; for(int i=0;i<len;++i){ int p=q[i]-'a'; if(!a[u].nxt[p]) a[u].nxt[p]=++cnt; u=a[u].nxt[p]; } a[u].end=1; } inline void match(int x){ //爆搜找最大匹配值 if(vis[x]) return ; vis[x]=1; ans=max(ans,x); int u=0; for(int i=x;i<len;++i){ int p=q[i]-'a'; if(!a[u].nxt[p]) return ; u=a[u].nxt[p]; if(a[u].end) match(i+1); //可以重头开始找 } } inline void query(){ read_q(); memset(vis,0,sizeof(vis)); ans=0; match(0); printf("%d ",ans); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) insert(); for(int i=1;i<=m;++i) query(); return 0; }