- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
由于新文章的做法与旧文章不同, 因此 KMP 算法仍保留旧文章, 且经过模板题测验, 新的做法明显慢于旧的做法, 但是, 新做法更好理解. 。
前缀 是指从串首开始到某个位置 \(i\) 结束的一个特殊子串. 。
真前缀 指除了 \(S\) 本身的 \(S\) 的前缀. 。
举例来说, 字符串 abcabeda 的所有前缀为 {a, ab, abc, abca, abcab, abcabe, abcabed, abcabeda} , 而它的真前缀为 {a, ab, abc, abca, abcab, abcabe, abcabed} . 。
后缀 是指从某个位置 \(i\) 开始到整个串末尾结束的一个特殊子串. 。
真后缀 指除了 \(S\) 本身的 \(S\) 的后缀. 。
举例来说, 字符串 abcabeda 的所有后缀为 {a, da, eda, beda, abeda, cabeda, bcabeda, abcabeda} , 而它的真后缀为 {a, da, eda, beda, abeda, cabeda, bcabeda} . 。
定义: 给定一个长度为 \(n\) 的字符串 \(s\) , 其前缀函数被定义为一个长度为 \(n\) 的数组 nxt . 其中 nxt[i] 是子串 s[0 ~ i] 最长的相等的真前缀和真后缀的长度. 。
用数学语言描述如下
特别地, nxt[0] = 0 , 因为不存在真前缀和真后缀. 。
举例来说, 对于字符串 aabaaab .
nxt[0] = 0 , a 没有真前缀和真后缀. 。
nxt[1] = 1 , aa 只有一对相等的真前缀和真后缀: a , 长度为 \(1\) . 。
nxt[2] = 0 , aab 没有相等的真前缀和真后缀. 。
nxt[3] = 1 , aaba 只有一对相等的真前缀和真后缀: a , 长度为 \(1\) . 。
nxt[4] = 2 , aabaa 相等的真前缀和真后缀有 a , aa , 最长的长度为 \(2\) . 。
nxt[5] = 2 , aabaaa 相等的真前缀和真后缀有 a , aa , 最长的长度为 \(2\) . 。
nxt[6] = 3 , aabaaab 相等的真前缀和真后缀只有 aab , 最长的长度为 \(3\) . 。
cin >> s1;
len1 = s1.length();
for (int i = 1; i < len1; ++ i) {
for (int j = i; j; -- j) {
if (s1.substr(0, j) == s1.substr(i - (j - 1), j)) {
nxt[i] = j;
break ;
}
}
}
第一个重要的观察是 相邻的前缀函数值至多增加 \(1\) . 。
参照下图所示, 只需如此考虑: 当取一个尽可能大的 nxt[i + 1] 时, 必然要求新增的 s[i + 1] 也与之对应的字符匹配, 即 s[i + 1] = s[nxt[i]] , 此时 s[i + 1] = s[i] + 1 . 。
所以当移动到下一个位置时, 前缀函数的值要么增加一, 要么维持不变, 要么减少. 。
当 s[i+1] != s[nxt[i]] 时, 我们希望找到对于子串 s[0 ~ i] , 仅次于 nxt[i] 的第二长度 \(j\) , 使得在位置 \(i\) 的前缀性质仍得以保持, 也即 s[0 ~ (j - 1)] = s[(i - j + 1) ~ i] :
如果我们找到了这样的长度 \(j\) , 那么仅需要再次比较 s[i + 1] 和 s[j] . 如果它们相等, 那么就有 nxt[i + 1] = j + 1 . 否则, 我们需要找到子串 s[0 ~ i] 仅次于 \(j\) 的第二长度 \(j_{2}\) , 使得前缀性质得以保持, 如此反复, 直到 \(j = 0\) . 如果 s[i + 1] != s[0] , 则 nxt[i + 1] = 0 . 。
观察上图可以发现, 因为 s[0 ~ nxt[i] - 1] = s[i - nxt[i] + 1 ~ i] , 所以对于 s[0 ~ i] 的第二长度 \(j\) , 有这样的性质
s[0 ~ j - 1] = s[i - j + 1 ~ i]= s[nxt[i] - j ~ nxt[i] - 1] 也就是说 \(j\) 等价于子串 s[nxt[i] - 1] 的前缀函数值 (你可以把上面的 \(i\) 换成 nxt[i] - 1 ), 即 j = nxt[nxt[i] - 1] . 同理, 次于 \(j\) 的第二长度等价于 s[j - 1] 的前缀函数值. 。
cin >> s1;
len1 = s1.length();
for (int i = 1; i < len1; ++ i) {
int j = nxt[i - 1];
while (j && s1[i] != s1[j]) {
j = nxt[j - 1];
}
if (s1[i] == s1[j]) {
++ j;
}
nxt[i] = j;
}
给定一个文本 \(t\) 和一个字符串 \(s\) , 我们尝试找到并展示 \(s\) 在 \(t\) 中的所有出现. 。
为了简便起见, 我们用 \(n\) 表示字符串 \(s\) 的长度, 用 \(m\) 表示文本 \(t\) 的长度. 。
我们构造一个字符串 \(s\) + # + \(t\) , 其中 # 为一个既不出现在 \(s\) 中也不出现在 \(t\) 中的分隔符. 。
接下来计算该字符串的前缀函数. 现在考虑该前缀函数除去最开始 \(n + 1\) 个值 (即属于字符串 \(s\) 和分隔符的函数值) 后其余函数值的意义. 根据定义, nxt[i] 为右端点在 \(i\) 且同时为一个前缀的最长真子串的长度, 具体到我们的这种情况下, 其值为与 \(s\) 的前缀相同且右端点位于 \(i\) 的最长子串的长度. 由于分隔符的存在, 该长度不可能超过 \(n\) . 而如果等式 nxt[i] = n 成立, 则意味着 \(s\) 完整出现在该位置 (即其右端点位于位置 \(i\) ). 注意该位置的下标是对字符串 \(s\) + # + \(t\) 而言的. 。
因此如果在某一位置 \(i\) 有 nxt[i] = n 成立, 则字符串 \(s\) 在字符串 \(t\) 的 \(i - (n - 1) - (n + 1) = i - 2n\) 处出现. 。
正如在前缀函数的计算中已经提到的那样, 如果我们知道前缀函数的值永远不超过一特定值, 那么我们不需要存储整个字符串以及整个前缀函数, 而只需要二者开头的一部分. 在我们这种情况下这意味着只需要存储字符串 \(s\) + # 以及相应的前缀函数值即可. 我们可以一次读入字符串 \(t\) 的一个字符并计算当前位置的前缀函数值. 。
因此 Knuth–Morris–Pratt 算法(简称 KMP 算法)用 \(O_{n + m}\) 的时间以及 \(O_{n}\) 的内存解决了该问题. 。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 1e6 + 5;
int nxt[N << 1];
char s1[N], s2[N], cur[N << 1];
inline void get_nxt(char* s) {
int len = strlen(s);
for (int i = 1; i < len; ++ i) {
int j = nxt[i - 1];
while (j && s[i] != s[j]) {
j = nxt[j - 1];
}
if (s[i] == s[j]) {
++ j;
}
nxt[i] = j;
}
}
int main() {
cin >> s1 >> s2;
scanf("%s%s", s1, s2);
strcpy(cur, s2);
strcat(cur, "#");
strcat(cur, s1);
get_nxt(cur);
int l1 = strlen(s1), l2 = strlen(s2);
for (int i = l2 + 1; i <= l1 + l2; ++ i) {
if (nxt[i] == l2) {
cout << i - 2 * l2 + 1 << '\n';
}
}
for (int i = 0; i < l2; ++ i) {
cout << nxt[i] << ' ';
}
return 0;
}
最后此篇关于「学习笔记」KMP算法的文章就讲到这里了,如果你想了解更多关于「学习笔记」KMP算法的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
OkHttp的作用 OkHttp is an HTTP client。 如果是HTTP的方式想得到数据,就需要我们在页面上输入网址,如果网址没有问题,就有可能返回对应的String字符串,如果这个地址
Record 一个重要的字符串算法,这是第三次复习。 通过总结我认为之所以某个算法总是忘记,是因为大脑始终没有认可这种算法的逻辑(也就是脑回路)。 本篇主要讲解从KMP的应用场景,
SQL 注入基础 【若本文有问题请指正】 有回显 回显正常 基本步骤 1. 判断注入类型 数字型 or 字符型 数字型【示例】:
标签: #Prompt #LLM 创建时间:2023-04-28 17:05:45 链接: 课程(含JupyterNotebook) , 中文版 讲师: An
Swift是供iOS和OS X应用编程的新编程语言,基于C和Objective-C,而却没有C的一些兼容约束。Swift采用了安全的编程模式和添加现代的功能来是的编程更加简单、灵活和有趣。界面则基于
红日靶机(一)笔记 概述 域渗透靶机,可以练习对域渗透的一些知识,主要还是要熟悉 powershell 语法,powershell 往往比 cmd 的命令行更加强大,而很多渗透开源的脚本都是 po
八大绩效域详细解析 18.1 干系人绩效域 跟干系人所有相关的活动. 一、预期目标 ①与干系人建立高效的工作关系 ②干系人认同项目目标 ③支持项目的干系人提高
18.3 开发方法和生命周期绩效域 跟开发方法,项目交付节奏和生命周期相关的活动和职能. 一、预期目标: ①开发方法与项目可交付物相符合; ②将项目交付与干系人价值紧密
18.7 度量绩效域 度量绩效域涉及评估项目绩效和采取应对措施相关的活动和职能度量是评估项目绩效,并采取适当的应对措施,以保持最佳项目绩效的过程。 一、 预期目标: ①对项目状况
pygraphviz 安装,windows系统: 正确的安装姿势: Prebuilt-Binaries/PyGraphviz at master · CristiFati/Prebuilt-Binar
今天给大家介绍IDEA开发工具如何配置devtools热加载工具。 1、devtools原理介绍 spring-boot-devtools是spring为开发者提供的热加载
一 什么是正则表达式 // 正则表达式(regular expression)是一个描述字符模式的对象; // JS定义RegExp类表示正则表达式; // String和RegExp都定义了使用
目前是2022-04-25 23:48:03,此篇博文分享到互联网上估计是1-2个月后的事了,此时的OpenCV3最新版是3.4.16 这里前提是gcc,g++,cmake都需要安装好。 没安装好的,
一、概述 1、Flink 是什么 Apache Flink is a framework and distributed processing engine for stateful comput
一、window 概述 Flink 通常处理流式、无限数据集的计算引擎,窗口是一种把无限流式数据集切割成有限的数据集进行计算。window窗口在Flink中极其重要。 二、window 类型 w
一、触发器(Trigger) 1.1、案例一 利用global window + trigger 计算单词出现三次统计一次(有点像CountWindow) 某台虚拟机或者mac 终端输入:nc -
一、时间语义 在Flink 中涉及到三个重要时间概念:EventTime、IngestionTime、ProcessingTime。 1.1、EventTime EventTime 表示日志事
一、概述 以wordcount为例,为什么每次输入数据,flink都能统计每个单词的总数呢?我们都没有显示保存每个单词的状态值,但是每来一条数据,都能计算单词的总数。事实上,flink在底层维护了每
一、概述 checkpoint机制是Flink可靠性的基石,可以保证Flink集群在某个算子因为某些原因(如 异常退出)出现故障时,能够将整个应用流图的状态恢复到故障之前的某一状态,保 证应用流图状
一、standalone 部署模式 1、下载安装包 下载安装包地址 有两种安装包类型: 第一种是带 Hadoop依赖的(整合YARN) 第二种是不带 Hadoop依赖的(Standalone模式)
我是一名优秀的程序员,十分优秀!