CF633C Spy Syndrome 2 trie树
2024-09-05 05:24:36
这个模型以前绝对见过,模拟赛的时候开始敲了一个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
*/
最新文章
- c++容器
- clip-path
- SQL分组和聚合(Grouping and Aggregates)
- 试用windows Azure
- java传输json数据用md5加密过程
- ios更改UITabBarController背景以及选中背景图片的方法
- C++ Prime:指针和const
- Guava源码分析——ServiceManager
- QT5.4 计算器程序 打包&;发布,解决dll的最新解决方案(图文并茂,很清楚)
- TFS(Team Foundation Server)简介和新手入门
- Drupal设置首页默认内容
- js获取当前url
- 再见了Server对象,拥抱IHostingEnvironment服务对象(.net core)
- bae64编码
- IFrame跨域访问&;&;IFrame跨域访问自定义高度
- leetcode1010
- poj2049
- HZNU_TI1050 训练实录
- scrapy-redis基础和介绍
- Linux命令-帮助命令:man