BZOJ 3670 NOI 2014 动物园 变形KMP
发布日期:2021-10-02 10:57:32 浏览次数:18 分类:技术文章

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

题目大意:定义一种前缀,这个前缀和后缀一样并且没有交集,num[i]为前i位有多少个这样的前缀,输出答案为,即

没资格写题解,因为我的KMP掌握的不好。推荐去看我同学的题解:http://blog.csdn.net/vmurder/article/details/38993639

CODE:

#include 
#include
#include
#include
#define MAX 1001000 #define MO 1000000007using namespace std;int cases;char s[MAX];long long pre[MAX],num[MAX];int fix1,fix2;int ans;inline void Initialize();inline void Work();int main(){ for(cin >> cases;cases; --cases) { Initialize(); scanf("%s",s + 1); Work(); cout << ans << endl; } return 0;}inline void Initialize(){ ans = 1; num[1] = 1;}inline void Work(){ for(int fix1 = 0,fix2 = 0,i = 2;s[i]; ++i) { while(fix1 && s[i] != s[fix1 + 1]) fix1 = pre[fix1]; if(s[i] == s[fix1 + 1]) fix1++; pre[i] = fix1; num[i] = num[fix1] + 1; while(fix2 && s[i] != s[fix2 + 1]) fix2 = pre[fix2]; if(s[i] == s[fix2 + 1]) fix2++; while(fix2 > (i >> 1)) fix2 = pre[fix2]; ans = (ans * (num[fix2] + 1)) % MO; }}

转载地址:https://blog.csdn.net/jiangyuze831/article/details/39009207 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:BZOJ 1503 郁闷的出纳员 二叉平衡树(Treap,Splay)
下一篇:BZOJ 3669 NOI 2014 魔法森林 最短路/LCT

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年03月29日 09时04分26秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

斥候密报_斥候密报《最强王者》三国幕后巾帼之黄月英_吉吉建站手游网 2019-04-21
python的循环控制结构是什么_7.Python控制和循环结构 2019-04-21
python 死循环插曲变量_FishC03 讲:python小插曲之变量和字符串 2019-04-21
车型代号对照表_车型代号对照表_相关文章专题_写写帮文库 2019-04-21
arcgis符号方向_ArcGIS制图表达-河流渐变与符号旋转 2019-04-21
springboot 实现机器学习_SpringBoot架构浅谈 2019-04-21
oss批量上传工具_OssExplorer一OSS的专用客户端工具【最新版】_Windows_Windows server 2008-云市场-阿里云... 2019-04-21
login控件authenticate_ASP:Login控件(登录控件) 2019-04-21
drf 安装_drf 安装与配置 2019-04-21
c++ loadlibrary 初始化对象_C++构造函数和初始化表 2019-04-21
jmeter mysql driver_jmeter测试mysql数据库之JDBC请求 2019-04-21
mysql group by cube_SQL Server 之 GROUP BY、GROUPING SETS、ROLLUP、CUBE 2019-04-21
mysql mgr 5.6_mysql MGR高可用配置 2019-04-21
lua 区间比较_TI-Lua 系列教程2.4.1: 条件分支 2019-04-21
mysql同时多表插入_MySQL多表同时插入 2019-04-21
postman delete 请求传递数组_Postman请求方法 2019-04-21
基于mysql学生签到_Java swing mysql学生签到考勤系统附带完整源码及开发视频 2019-04-21
go mysql 多并发_MySQL并发处理-Go语言中文社区 2019-04-21
mysql定义变量字符串类型_mysqli_stmt :: bind_param():类型定义字符串中的元素数量与绑定变量的数量不匹配... 2019-04-21
mysql测试数据100w_利用MySQL存储过程批量插入100W条测试数据 2019-04-21