HDU 1686 :Oulipo
发布日期:2021-06-30 16:05:56
浏览次数:2
分类:技术文章
本文共 520 字,大约阅读时间需要 1 分钟。
KMP题
不过这次是求单词在文本中出现的次数一种很容易想到的方法:当单词与文本匹配成功后,文本退回到与单词匹配成功的第一个字符的后一个字符,单词退回到第一个字符,再重新进行匹配,这样显然会超时
其实单词与文本匹配成功后,文本并不需要退回,我们可以这样认为:
当单词与文本匹配成功后,我们假设单词位置m上存在字符(其实是不存在的,因为单词字符的位置范围 [0,m-1]),那么此时单词位置 [0,m-1]上 的字符都与文本匹配成功了,所以文本继续向后移动一个字符到位置a,单词也继续向后移动一个字符到位置m,显然单词不存在位置m这个字符,所以我们认为这次匹配失败,所以文本a位置字符应该跟单词 fail[m] 位置字符进行匹配,这样就满足题目的时间限制了
具体看代码:
#include#include using namespace std;const int maxn=10000+100;char ch[maxn*100],ph[maxn];int fail[maxn];int n,m;inline void getFail(){ fail[0]=fail[1]=0; for(int i=1;i
转载地址:https://kaven.blog.csdn.net/article/details/81176092 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月26日 19时49分16秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
理解HTTPS为什么安全前,先看看这些东西
2019-05-01
代码这样写不止于优雅(Python版)
2019-05-01
一份来自掘金社区的开发者报告
2019-05-01
只有1%的程序员搞懂过浮点数陷阱
2019-05-01
Erlang 之父 Joe Armstrong 去世
2019-05-01
速来,上期中奖名单
2019-05-01
一名 Google 工程师的大数据处理经验
2019-05-01
30分钟学会pyecharts数据可视化
2019-05-01
从一个骗子身上学到的
2019-05-01
关于Python爬虫,这里有一条高效的学习路径
2019-05-01
Python学习指南,看这篇清晰多了!
2019-05-01
Oracle裁员,3点建议
2019-05-01
「忙」只是借口
2019-05-01
如果只有1小时学Python,看这篇就够了
2019-05-01
命名难,难于上青天
2019-05-01
记一件小事
2019-05-01
掌握 Python 爬虫的所有技巧,都在这里!
2019-05-01
史上最烂项目:苦撑12年,600多万行代码...
2019-05-01
斯坦福后空翻机器人设计、代码全开源,成本降至3000美元,人人皆可DIY
2019-05-01
618|Python购书攻略
2019-05-01