博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CF633C:Spy Syndrome 2——题解
阅读量:6231 次
发布时间:2019-06-21

本文共 1276 字,大约阅读时间需要 4 分钟。

#include
#include
#include
#include
using namespace std;const int M=1001000;int n,m,dp[M],l[M],tot=1,now,ll,pos[M];char s[M],t[M];vector
v;struct node{ int ed,son[26]; node(){ ed=0; memset(son,0,sizeof(son)); }}tree[1000001];void insert(int k){ now=1; int q; for(int i=ll+1;i<=l[k]+ll;i++){ if(t[i]<'a')q='a'-'A';else q=0; if(tree[now].son[t[i]-'a'+q]==0){ tot++; tree[now].son[t[i]-'a'+q]=tot; } now=tree[now].son[t[i]-'a'+q]; } tree[now].ed=k; return;}int main(){ cin>>n; cin>>s+1; cin>>m; for(int i=1;i<=m;i++){ cin>>t+ll+1; pos[i]=ll+1; l[i]=strlen(t+ll+1); insert(i); ll+=l[i]; } dp[0]=1; for(int i=1;i<=n;i++){ now=1; for(int j=1;j<=i&&now;j++){ now=tree[now].son[s[i-j+1]-'a']; if(tree[now].ed&&dp[i-j]){ dp[i]=tree[now].ed; break; } } } for(int i=n;i>=1;i-=l[dp[i]]){ v.push_back(dp[i]); } int ss=v.size(); for(int i=ss-1;i>=0;i--){ for(int j=1;j<=l[v[i]];j++){ putchar(t[pos[v[i]]+j-1]); } putchar(' '); } return 0;}

 

转载于:https://www.cnblogs.com/luyouqi233/p/7880037.html

你可能感兴趣的文章
Oracle中shrink space命令详解
查看>>
验证码 生成变形的文字
查看>>
用cflow工具生成代码函数调用关系【转】
查看>>
ASP.NET MVC5+EF6+EasyUI 后台管理系统(75)-微信公众平台开发-用户管理
查看>>
android用户界面之菜单(Menu)教程实例汇总
查看>>
单链表
查看>>
linux下的僵尸进程处理SIGCHLD信号【转】
查看>>
c#中volatile关键字的作用
查看>>
Hadoop概念学习系列之搭建(windows)Eclipse/MyEclipse远程操作(Linux上)hadoop2.2.0/hadoop2.6.0 出错集(三十五)...
查看>>
淘米水的10大功效
查看>>
android 中如何分析内存泄漏
查看>>
关于简明Vim练级攻略
查看>>
遇到不可重现问题怎么办
查看>>
ASP.NET MVC5+EF6+EasyUI 后台管理系统(57)-插件---ueditor使用
查看>>
swift-数组array
查看>>
jQuery插件开发学习笔记
查看>>
现代软件工程 第十三章 【软件测试】 练习与讨论
查看>>
SharePoint Framework 开发工具和库
查看>>
团队项目建议 - 英语学习 App
查看>>
30个非常流行的提示信息插件(jQuery Tooltip Plugin)
查看>>