串ababaaababaa的next和串ababaabab的nextval

简介: 本文介绍了计算字符串的next数组和nextval数组的方法,通过分析两个具体的例子来展示如何计算这些数组,这些数组通常用于KMP算法中。

这个next求法我看了视频和网上的,发现有两种求法,一种是求最左边和最右边相等的最大个数,

就比如说串ababaaababaa,这个

所以这个3的位置为1,依次下来。

这个唯一要注意的是,是按照你选择的前一项的next决定你匹配的个数,就比如说第五号位置

的前一项的4号的next为2,所以先看最前面2个和最左边两个,一看ab 和ab 就匹配了,匹配加一就是第五号的next的值,如果前一项最大匹配匹配不了才看有多少匹配的,就比如说第7号位置的前一项的next是4所以匹配4个,结果一看abab不和abaa匹配,这时就要看最左边和最右边能匹配多少的最左边为a,最右边为a,就匹配的了一个,一个加一就是2了,这个最左边就是第一号位置,最右边就是第七号的前面。你选那个就是那个的前面。

nextval的求法就是按照next求

目录
相关文章
|
6月前
|
存储 算法 程序员
串是什么,串存储结构的3种实现方法
串是什么,串存储结构的3种实现方法
108 8
|
C语言
带你快速了解字符(串)函数(一)
带你快速了解字符(串)函数(一)
|
3月前
|
算法 C++
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现,包括计算模式串的next数组和在主串中查找模式串位置的函数,用于演示KMP算法的基本应用。
|
3月前
|
算法 C++
B : DS串应用–串替换
这篇文章介绍了如何使用KMP算法在给定的主串中查找模式串的位置,并用替换串替换模式串的C++程序实现,仅考虑单次替换情况。
带你快速了解字符(串)函数(二)
带你快速了解字符(串)函数(二)
带你快速了解字符(串)函数(三)
带你快速了解字符(串)函数(三)
|
6月前
【每日一题Day203】LC1016子串能表示从 1 到 N 数字的二进制串 | 枚举 哈希表
【每日一题Day203】LC1016子串能表示从 1 到 N 数字的二进制串 | 枚举 哈希表
48 2
|
6月前
【每日一题Day237】LC1375二进制字符串前缀一致的次数 | 技巧题
【每日一题Day237】LC1375二进制字符串前缀一致的次数 | 技巧题
50 1
|
6月前
leetcode-1784:检查二进制字符串字段
leetcode-1784:检查二进制字符串字段
34 0
|
存储 算法 C语言
串、串的模式匹配算法(子串查找)BF算法、KMP算法
串、串的模式匹配算法(子串查找)BF算法、KMP算法