这个模型以前绝对见过,模拟赛的时候开始敲了一个AC自动机,纯属脑抽~

code:

#include <bits/stdc++.h>
#define N 5000006
#define NN 10005
#define M 100006
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
queue<int>q;
stack<int>ss;
int n,m,cnt,tot;
int st[M],ed[M],f[M],lst[M],length[M];
char S[M],str[M],total[N];
struct Node
{
int tag,f,len;
map<int,int>ch;
}t[N];
int main()
{
int i,j;
// setIO("char");
scanf("%d",&n);
scanf("%s",S+1);
scanf("%d",&m);
for(i=1;i<=m;++i)
{
scanf("%s",str+1);
int len=strlen(str+1);
int p=0;
st[i]=cnt+1;
ed[i]=st[i]+len-1;
for(j=1;j<=len;++j)
{
int c;
total[++cnt]=str[j];
if(str[j]>='A'&&str[j]<='Z') c=str[j]-'A';
else c=str[j]-'a';
if(!t[p].ch[c])
{
t[p].ch[c]=++tot;
}
p=t[p].ch[c];
}
t[p].tag=i;
t[p].len=len;
}
f[0]=1;
for(i=1;i<=n;++i)
{
int p=0,step=0;
for(j=i;j>=1;--j)
{
++step;
int c=S[j]-'a';
if(t[p].ch[c])
{
p=t[p].ch[c];
if(t[p].tag && f[j-1])
{
f[i]=1;
lst[i]=t[p].tag;
length[i]=t[p].len;
break;
}
}
else
{
break;
}
}
}
for(i=n;i;i-=length[i])
{
ss.push(lst[i]);
}
while(!ss.empty())
{
int u=ss.top(); ss.pop();
for(i=st[u];i<=ed[u];++i) printf("%c",total[i]);
printf(" ");
}
return 0;
}
/*
orz rjj
*/

  

最新文章

  1. c++容器
  2. clip-path
  3. SQL分组和聚合(Grouping and Aggregates)
  4. 试用windows Azure
  5. java传输json数据用md5加密过程
  6. ios更改UITabBarController背景以及选中背景图片的方法
  7. C++ Prime:指针和const
  8. Guava源码分析——ServiceManager
  9. QT5.4 计算器程序 打包&amp;发布,解决dll的最新解决方案(图文并茂,很清楚)
  10. TFS(Team Foundation Server)简介和新手入门
  11. Drupal设置首页默认内容
  12. js获取当前url
  13. 再见了Server对象,拥抱IHostingEnvironment服务对象(.net core)
  14. bae64编码
  15. IFrame跨域访问&amp;&amp;IFrame跨域访问自定义高度
  16. leetcode1010
  17. poj2049
  18. HZNU_TI1050 训练实录
  19. scrapy-redis基础和介绍
  20. Linux命令-帮助命令:man

热门文章

  1. vuex 理解
  2. k8s基础环境搭建
  3. LaTeX技巧96:LaTeX 图片控制命令,位置控制
  4. idea jetty:run 启动
  5. JS OOP 概述
  6. Django rest-framework框架-组件之视图
  7. vue兄弟组件的传值eventbus
  8. python多线程与多进程异步事件框架
  9. 5.管道 Pipe
  10. 案例:selenium实现登录处理弹窗