【bzoj3620】【似乎在梦中见过的样子】【kmp】
发布日期:2021-11-16 15:38:36 浏览次数:23 分类:技术文章

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

Description

“Madoka,不要相信 QB!”伴随着 Homura 的失望地喊叫,Madoka 与 QB 签订了契约.
这是 Modoka 的一个噩梦,也同时是上个轮回中所发生的事.为了使这一次 Madoka 不再与 QB
签订契约,Homura 决定在刚到学校的第一天就解决 QB.然而,QB 也是有许多替身的(但在第八话
中的剧情显示它也有可能是无限重生的),不过,意志坚定的 Homura 是不会放弃的——她决定
消灭所有可能是 QB 的东西.
现在,她已感受到附近的状态,并且把它转化为一个长度为 n 的字符串交给了学 OI 的你.
现在你从她的话中知道 , 所有形似于 A+B+A 的字串都是 QB 或它的替身 , 且
len(A)>=k,len(B)>=1 (位置不同其他性质相同的子串算不同子串,位置相同但拆分不同的子串
算同一子串),然后你必须尽快告诉 Homura 这个答案——QB 以及它的替身的数量.

Input

第一行一个字符串,第二行一个数 k

Output

仅一行一个数 ans,表示 QB 以及它的替身的数量

Sample Input

【样例输入 1】
aaaaa
1
【样例输入 2】
abcabcabc
2

Sample Output

【样例输出 1】
6

【样例输出 2】
8

HINT

对于 100%的数据:n<=15000 , k<=100,且字符集为所有小写字母

题解:枚举左端点,然后扩展kmp即可.

代码:

#include
#include
#include
#define N 20000using namespace std;char s[N],ss[N];int ans,k,j,fail[N],len;int main(){ scanf("%s",s+1);scanf("%d",&k);len=strlen(s+1); for (int i=1;i<=len;i++) if (len-i+1>k*2){ for (int p=i;p<=len;p++) ss[p-i+1]=s[p]; j=0; for (int p=2;p<=len-i+1;p++){ while (j&&ss[j+1]!=ss[p]) j=fail[j]; if (ss[j+1]==ss[p]) j++; fail[p]=j; } j=0; for (int p=1;p<=len-i+1;p++){ while (j&&ss[j+1]!=ss[p]) j=fail[j]; if (ss[j+1]==ss[p]) j++; int jj=j; while (jj&&(jj<<1>=p)) jj=fail[jj]; ans+=jj>=k; } // cout<
<<' '<
<

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

上一篇:【bzoj1954】【The xor-longest Path】【trie树】
下一篇:【bzoj3165】【HEOI2013】【Segment】【线段树】

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2024年03月23日 05时00分45秒

关于作者

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

推荐文章

java wav 切割_java切割音频文件 2019-04-21
java获取服务器编码_使用Java代码获取服务器性能信息及局域网内主机名 2019-04-21
mysql 导出json_如何将MySQL数据库导出到JSON? 2019-04-21
嵌入式Linux咨询公司,Technical support and consulting 2019-04-21
linux 离线安装中文字库,centos7 离线安装字体fontconfig 2019-04-21
可以使用鸿蒙系统的55款手机,华为鸿蒙系统首批适配机型即将公布,共有55款产品可升级搭载... 2019-04-21
鸿蒙系统chromeos2.0,【华为鸿蒙系统】鸿蒙OS 2.0 适配计划曝光 2019-04-21
android高德地图设置缩放级别,设置地图中心点/级别 2019-04-21
dv4 安装linux,linux安装中的问题 2019-04-21
gmat阅读.html,GMAT阅读“Ecoefficiency”文章深度分析 2021-06-24
html5 带图片导航,html5 带声音的导航 2021-06-24
point 如何求elbow_机器人学——实践一(Arm Navigation 理论+代码) 2021-06-24
avs3 mkv格式封装_将你的视频无损封装成MP4,非转码哦! 2021-06-24
java http服务端_HTTP协议经典面试题整理及答案详解 2021-06-24
mysql 递归查找父节点_数据结构与算法—浅显易懂的二叉排序(查找)树 2021-06-24
body里写注释 postman_使用 Postman 做 API 自动化测试 2021-06-24
python3的配置文件类单例实现_Servlet是单例还多例 2019-04-21
写一个饿汉单例模式的例子_看完这篇单例模式,终于敢和面试官对线了 2019-04-21
华为手机的分类有何区别_动画有哪些分类?又有何区别? 2019-04-21
wxpython 表格重置_wxpython清除小部件并创建新布局 2019-04-21