【数据结构&算法】10-串基础&KMP算法源码【数据结构&算法】10-串基础

前言
串的定义
串的比较
串的抽象类型数据
- 串与线性表的比较
- 串的数据
串的存储结构
- 串的顺序存储结构
- 串的链式存储结构
朴素的模式匹配算法
- 模式匹配的定义
- 朴素的匹配方法（BRUTE FORCE 算法，BF 算法）
- 时间复杂度分析
KMP 模式匹配算法
- KMP 与 BF 算法
- KMP 算法原理
- 模式串向右移动距离的计算
- 基于 next 的 KMP 算法的实现
- KMP 时间复杂度
参考代码
- 串 & KPM 算法

前言李柱明博客：https://www.cnblogs.com/lizhuming/p/15487367.html
串的定义定义：

串（string）：由零个或多个字符组成的有限序列，又名叫字符串。

相关概念：

空格串：只包含空格的串。
- 注意：与空串区别，空格串是有内容有长度的，而且可以不止一个空格。
子串：串中任意个数的连续字符组成的子序列，称为该串的子串。
【【数据结构&算法】10-串基础&KMP算法源码】主串：相应地，包含子串的串，称为主串。
子串在主串中的位置：子串的第一个字符在主串中的序号。

串的比较串的比较：

通过组成串的字符之间的编码来进行的。
而字符的编码：指的是字符在对应字符集中的序号。

ASCII 和 Unicode：

ASCII 码：用 8 个二进制数表示一个字符，总共可以表示 256 个字符。
Unicode 码：用 16 位二进制数表示一个字符，总共有 2 的 16 次方个字符。
为了和 ASCII 码兼容，Unicode 码的前 256 个字符与 ASCII 码完全相同。

串相等：

长度相等，各个对应位置的字符相等。

串的抽象类型数据串与线性表的比较
线性表：更关注单个元素的操作，如查找一个元素，插入或删除一个元素。
串：更多是查找子串位置、得到指定位置子串、替换子串等操作。
串的数据
数据：串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
操作：

str_assign(t, *cahrs); 生成一个其值等于字符串常量 chars 的串 t。
str_copy(t, s); 串 s 存在，由串 s 复制得到串 t 中。
str_clear(s); 清空串。
str_empty(s); 判断串是否空。
str_length(s); 串的长度。
str_compare(s, t); 若 s>t，返回 >0 ，若 s=t ，返回 0 ，若 s
str_concat(t, s1, s2); 合并 s1 和 s2，通过 t 返回。
str_get_sub(t, s, pos, len); 在串 s 中从 pos 点开始截取最大 len 的长度，通过 t 返回。
str_index(s, t, pos); 在主串 s 的 pos 位置起查找子串 t 并返回起始子串起始位置，没有则返回 0。
str_replace(s, t, v); 在主串 s 中查找子串 t，并用串 v 代替。
str_insert(s, pos, t); 在主串 s 的 pos 位置中插入串 t。
str_delete(s, pos, len); 在主串 s 中的 pos 位置其删除长度为 len 的子串。

串的存储结构串的存储结构与线性表类似，分为两类：顺序和链式。
串的顺序存储结构
定义：用一组地址连续的存储单元来存储串中的字符序列。
按照预定义大小，为每个定义的串分配一个固定长度的存储区，一般用定长数组来定义。
一般可以将实际的串长值保存在数组的 0 下标位置，或者在数组的最后一个下标位置。
但有的语言规定在串值后面加一个不计入串长度的结束标记符号“\0”来表示串值的终结（但占用一个空间）。
由于过于不便，串的顺序存储操作有一些变化：串值的存储空间可在程序执行过程中动态分配而得

比如堆：可由 c 语言动态分配函数 malloc() 和 free()来管理。

串的链式存储结构
定义：用节点保存串的数据。
若一个结点存放一个字符，会存在很大的空间浪费。
故串的链式可以一个结点放多个字符，最后一个结点若不满，可用#或其他非串值字符补全。（每个节点固定长度）

文章图片

优点：连接两串操作方便。
缺点：灵活度、性能都不如顺序存储结构的。
朴素的模式匹配算法模式匹配的定义
子串（又称模式串）的定位操作通常称做串的模式匹配，是串中最重要的操作之一。
朴素的匹配方法（BRUTE FORCE 算法，BF 算法）
逻辑思路：

对主串的每个字符作为子串开头，与要匹配的字符串进行匹配。
对主串做大循环，每个字符开头做要匹配子串的长度的小循环，直到匹配成功或全部遍历完成为止。

数据结构：

typedef struct{ char *str; int max_length; int length; }data_str_t;

代码实现：

int bf_index(data_str_t main_str, int start, data_str_t sub_str) { int i = start, j = 0, v; while ((i < main_str.length)&&(j < sub_str.length)) { if(main_str.str[i] == sub_str.str[j]) { i++; j++; } else { i = i - j + 1; j = 0; } } if (j == sub_str.length) { v = i-sub_str.length; } else { v = -1; } return v; }

时间复杂度分析
n：主串长度，m：要匹配子串长度。
时间复杂度分析：

最好情况：O(1)
- 第一次比较就找到。
平均情况：O(n+m)
- 根据等概率原则，平均是(n+m)/2 次查找。
最坏的情况： O(m×n) （注：(n-m+1)×m）
- 每遍比较都在最后出现不等，即每遍最多比较 m 次，最多比较 n-m+1 遍，总的比较次数最多为 m(n-m+1)。

KMP 模式匹配算法 KMP 与 BF 算法
KMP 算法：

由三位前辈发表的一个模式匹配算法，可以大大避免重复遍历的情况，称之为克努特-莫里斯-普拉特算法，检查 KMP 算法。
又叫快速模式匹配算法。

KMP 算法相比于 BF 算法，优势在于：

在保证指针 i 不回溯的前提下，当匹配失败时，让模式串向右移动最大的距离；
并且可以在 O(n+m) 的时间数量级上完成对串的模式匹配操作。

KMP 算法原理
参考链接：CSDN
原理：

主串 S 与模式串 T 有部分相同子串时，可以简化朴素匹配算法中的循环流程。
KMP 中的关键就是求公共最长匹配前缀和后缀的长度。
- 从子串最长前缀和最长后缀开始求。最长也少于前面字符个数。
- 最长公共前缀的后面一个字符（指针 j）和匹配失败的那个字符（指针 i）进行对比。
  - 若匹配相同，则继续推荐 i 和 j。
  - 若匹配不同，则继续缩短公共最长前缀和后缀。就是指针 j 进行参考 next 数组回溯。
- 文章图片
例子 1，如下图：跳过主串和子串相同的部分。
- 前提：要先知道模式串 T 中首字符 ‘a’ 与串 T 后面的字符均不相等。
  
  文章图片
例子二，如下图：跳过子串中与首字符相同的字符。

文章图片

模式串向右移动距离的计算
在模式串和主串匹配时，各有一个指针指向当前进行匹配的字符（主串中是指针 i ，模式串中是指针 j ）。
在保证 i 指针不回溯的前提下，如果想实现功能，就只能让 j 指针回溯。
j 指针回溯的距离，就相当于模式串向右移动的距离。 j 指针回溯的越多，说明模式串向右移动的距离越长。
计算模式串向右移动的距离，就可以转化成：当某字符匹配失败后， j 指针回溯的位置。
模式串中的每个字符所对应 j 指针回溯的位置，可以通过算法得出，得到的结果相应地存储在一个数组中（默认数组名为 next ）。

即是模式串中遇到某个字符匹配失败，就在 next 数组中找到对应的回溯位置，取出该位置对应的字符和当前的字符继续匹配，直至全部匹配失败再推进主串指针 i 和模式串指针 j。

计算方法：

对于模式串中的某一字符来说，提取它前面的字符串，分别从字符串的两端查看连续相同的字符串的个数，在其基础上 +1 ，结果就是该字符对应的值。
注意：
- 字符对应 next 是第 0 个字符对应 next 数组下标为 1 开始的。
- 前面两个字符对应的回溯值为 0、1。

例子：求模式串 “abcabac” 的 next 。

第 1 个字符：‘a’，next 值为 0。
第 2 个字符：‘b’，next 值为 1。
第 3 个字符：‘c’，提取字符串 ‘ab’，连续系统字符为 0 个。0 + 1 = 1。 next 值为 1。
第 4 个字符：‘a’，提取字符串 ‘abc’，连续系统字符为 0 个。0 + 1 = 1。 next 值为 1。
第 5 个字符：‘b’，提取字符串 ‘abca’，连续系统字符为 1 个。1 + 1 = 2。 next 值为 2。
第 6 个字符：‘a’，提取字符串 ‘abcab’，连续系统字符为 2 个。2 + 1 = 3。 next 值为 3。
第 7 个字符：‘c’，提取字符串 ‘abcaba’，连续系统字符为 1 个。1 + 1 = 2。 next 值为 2。
由上的 next 数组的值为（从下标为 1 开始） [0, 1, 1, 1, 2, 3, 2]。

代码实现：

理解：下图为 demo
- 文章图片
- 理解字符串和 next 数组的下标都为 1 开始。（可以从 0 开始，自己留意下就可以了，不影响原理）
- 计算 next 数组的值只需要模式串即可，求出每个字符匹配失败时指针 j 回溯的长度。
- 在求 next 数组的值得过程中：
  - 不要采用暴力算法检索模式串。
    - 即是不要从可能最长的公共前后缀开始一个减一个地对比下去。如求图中 j+1 的 next 值时，暴力算法就是对比 aabcaabcaa 和 abcaabcaab，如果失败就减少一个长度继续重新对比 aabcaabca 和 bcaabcaab。然后循环下去。
  - 应该采用 KMP 算法（对，就是在 KMP 算法中利用 KMP 算法思维）检索模式串。
    - 即是如求图中 j+1 的 next 值时，直接取出 j 的 next 值 k 对应的字符 b（j 匹配时的最长公共前后缀，从最长的公共前后缀下手），对比 j 和 k 对应的字符。
      - 如匹配相同，则 k+1 （在上一个字符的最长公共前后缀基础上在加长一个字符）就是 j+1 对应字符的 next 值。
      - 若匹配不同，噢，匹配不同，后缀和前缀匹配时不同噢，主串和模式串匹配时不同噢，那就找出后缀（主串）和前缀（模式串）的公共前后缀，在这里前缀（主串）和后缀（模式串）是一样的，就是找出前缀（模式串）的公共前后缀部分（或者说 k 匹配失败时怎么办，利用 next 回溯啊）。就是找出 k 对应的公共前后缀部分，我们已经求出来了啊，就是 next[k] k'。k' 对应的字符和 j 对应的字符继续对比，若匹配相同，就 next[j] = k'+1，若匹配不同就继续缩短最长公共前后缀，最长就是 k' 对应字符的最长公共前后缀 next[k']。
      - 不说了，这样应该能看出递归了吧。直至最长公共前后缀为 0 时，采用特殊处理，因为这里下标 0 没有对应的字符，所以就推进 i 和 j，就是模式串的首字符和主串的下一个字符继续比较。看代码吧，骚年！！
      - 文章图片
- 利用上一个字符对应的 next 值，取出对应的字符，比较当前字符。
  1. 如果相等。当前字符的 next 值为上一个 next 值 + 1。结束。
  2. 如果不等，就拿上一个 next 的值做 next 的下标，继续取出字符对比。直至字符相等或循环到 next[1] = 0 结束。
    1. 循环获取下标 j 就是不断回溯 j。
注意：
- next 数组使用的下标初始值为 1 ，next[0] 没有用到（也可以存放 next 数组的长度）。
- 而串的存储是从数组的下标 0 开始的，所以程序中为 str[i-1] 和 str[j-1]。
初版（下面代码只提供思路，具体代码参考最后）：

#include #include /** * @namenext_creat * @brief简版。时间复杂度O(n) * @param * @retval * @author */ void next_creat(char *str, int *next) { int i = 1; next[1] = 0; int j = 0; while (i



 
  
 优化版（下面代码只提供思路，具体代码参考最后）：

 
 
 初版有个弊端，如模式串 caaaaabx。

 
 
用初版思维推导下，会发现当最后一个 a 匹配失败时需要回溯，但是前面的最长公共前后缀都是-1，不就是和暴力算法一样的效果吗。 
另外既然最后一个字符 a 匹配不成功，那前面连续的 a 肯定匹配不成功的，所以就应该直接回溯到前面连续字符的前一个字符 c。参考下面代码或者看大话数据结构 P142 页。 
  
 根据第 j 个的 next 值找它的 next 值 x 对应的第 x 个字符，并判断第 j 个和第 x 个字符是否相等。

  
 若不相等，保持 val 值等于 next 值；若相等，val 值等于第 x 个值的 val 值。

  
  
  
 #include 
#include /**
 * @namenext_creat
 * @brief优化版。时间复杂度O(n)
 * @param
 * @retval 
 * @author
 */
void nextval_creat(char *str, int *nextval)
{
int i = 1;

nextval[1] = 0;

int j = 0;

while (i


 
 基于 next 的 KMP 算法的实现

 
 KMP 算法（下面代码只提供思路，具体代码参考最后）：

 
 /**
 * @namekmp_index
 * @brief
 * @param
 * @retval 
 * @author
 */
int kmp_index(char *str_main, char *str_sub)
{
int i = 1;

int j = 1;

int next[10];
next_creat(str_sub, next);
//根据模式串T,初始化next数组while (i<=strlen(str_main) && j<=strlen(str_sub)) 
{
//j==0:代表模式串的第一个字符就和指针i指向的字符不相等；S[i-1]==T[j-1],如果对应位置字符相等，两种情况下，指向当前测试的两个指针下标i和j都向后移
if (j==0 || str_main[i-1] == str_sub[j-1]) 
{
i++;

j++;

}
else
{
j=next[j];
//如果测试的两个字符不相等，i不动，j变为当前测试字符串的next值
}
}
if (j > strlen(str_sub)) 
{
//如果条件为真，说明匹配成功
return i-(int)strlen(str_sub);

}
return -1;

}


 
 KMP 时间复杂度

 
 KMP 算法的时间复杂度：O(m+n)

 
  
get_next 的时间复杂度：O(m) 
while 循环的时间复杂度：O(n) 
  
 参考代码 
 串 & KPM 算法

 
 /** @filestring_kmp.c
 *@brief采用kmp算法
 *@details详细说明
 *@authorlzm
 *@date2021-09-11 20:10:56
 *@versionv1.0
 *@copyrightCopyright By lizhuming, All Rights Reserved
 *@bloghttps://www.cnblogs.com/lizhuming/
 *
 **********************************************************
 *@LOG 修改日志:
 **********************************************************
*/#include 
#include 
#include #define STRING_SIZE 100/* status_e是函数的类型,其值是函数结果状态代码，如OK等 */
typedef enum {
LZM_STRING_STATUS_ERR = -1,
LZM_STRING_STATUS_OK,
LZM_STRING_STATUS_FALSE,
}status_e;
typedef int elem_type;
	/* elem_type类型根据实际情况而定，这里假设为int */typedef char string_t[STRING_SIZE+1];
/**
 * @namestr_assing
 * @brief生成一个其值等于 str_t 的串 str_s
 * @param
 * @retval 
 * @author lzm
 */
status_e str_assing(string_t str_s, char *str_t)
{
int i = 0;
	if(str_t == NULL || str_s == NULL || strlen(str_s) > STRING_SIZE)
return LZM_STRING_STATUS_ERR;

	else
	{
str_t[0] = strlen(str_s);
for(i = 1;
 i <= str_t[0];
 i++)
str_t[i] = *(str_s + i-1);
return LZM_STRING_STATUS_OK;

	}
}/**
 * @namestr_copy
 * @brief复制串 str_t 到串 str_s
 * @param
 * @retval 
 * @author lzm
 */
status_e str_copy(string_t str_s, string_t str_t)
{ 
	int i = 0;
if(str_s == NULL || str_t == NULL)
{
return LZM_STRING_STATUS_ERR;

}	for(i = 0;
 i <= str_t[0];
 i++)
{
str_s[i] = str_t[i];

}	return LZM_STRING_STATUS_OK;

}/**
 * @namestr_empty
 * @brief判空
 * @param
 * @retval 
 * @author lzm
 */
status_e str_empty(string_t str_t)
{ 
if(str_t == NULL)
{
return LZM_STRING_STATUS_ERR;

}	if(str_t[0] == 0)
return LZM_STRING_STATUS_OK;
	return LZM_STRING_STATUS_FALSE;

}/**
 * @namestr_compare
 * @brief
 * @param
 * @retval str_s > str_t 则返回大于0，等就0， 小就负
 * @author lzm
 */
int str_compare(string_t str_s, string_t str_t)
{ 
	int i = 0;
if(str_t == NULL || str_s == NULL)
{
return LZM_STRING_STATUS_ERR;

}for(i = 1;
 i <= str_s[0] && i <= str_t[0];
 ++i)
if(str_s[i] != str_t[i])
return str_s[i] - str_t[i];
	return str_s[0] - str_t[0];

}/**
 * @namestr_length
 * @brief获取长度
 * @param
 * @retval 
 * @author lzm
 */
int str_length(string_t str_s)
{ 
if(str_s == NULL)
{
return LZM_STRING_STATUS_ERR;

}	return str_s[0];

}/**
 * @namestr_clear
 * @brief清空
 * @param
 * @retval 
 * @author lzm
 */
int str_clear(string_t str_s)
{ 
if(str_s == NULL)
return LZM_STRING_STATUS_ERR;
str_s[0] = 0;
	return LZM_STRING_STATUS_OK;

}/**
 * @namestr_concat
 * @brief拼接
 * @param
 * @retval 
 * @author lzm
 */
int str_concat(string_t str_t, string_t str_s1, string_t str_s2)
{
int i = 0;
if(str_t == NULL || str_s1 == NULL || str_s2 == NULL)
return LZM_STRING_STATUS_ERR;
if(str_s1[0] + str_s2[0] <= STRING_SIZE)
	{ 
/*未截断 */
for(i=1;
 i<=str_s1[0];
 i++)
str_t[i] = str_s1[i];
for(i=1;
 i <= str_s2[0];
 i++)
str_t[str_s1[0]+i]=str_s2[i];
str_t[0] = str_s1[0] + str_s2[0];
return LZM_STRING_STATUS_OK;

	}
	else if(str_s1[0] <= STRING_SIZE)
	{ 
/*截断S2 */
for(i=1;
 i <= str_s1[0];
 i++)
str_t[i] = str_s1[i];
for(i=1;
i<=STRING_SIZE-str_s1[0];
 i++)
str_t[str_s1[0]+i] = str_s2[i];
str_t[0] = STRING_SIZE;
return LZM_STRING_STATUS_FALSE;

	}
else
{
return LZM_STRING_STATUS_ERR;

}
}/**
 * @namestr_insert
 * @brief插串str_t入串str_s
 * @param
 * @retval 
 * @author lzm
 */
int str_insert(string_t str_s, string_t str_t, int pos)
{
int i = 0;
if(str_t == NULL || str_s == NULL || pos < 1 || pos > str_t[0]+1)
{
return LZM_STRING_STATUS_ERR;

}	if(str_s[0] + str_t[0] <= STRING_SIZE)
	{ 
/*完全插入 */
for(i=str_s[0];
 i>=pos;
 i--)
str_s[i+str_t[0]]=str_s[i];
 // 先挪动str_s串腾出空间for(i=pos;
 i str_s[0]-len+1)
return LZM_STRING_STATUS_ERR;
for(i=pos+len;
i<=str_s[0];
i++)
str_s[i-len] = str_s[i];
str_s[0]-=len;
	return LZM_STRING_STATUS_ERR;

}/**
 * @namenext_creat
 * @brief优化版。时间复杂度O(n)
 * @param
 * @retval 
 * @author
 */
int nextval_creat(char *str, int *nextval)
{
int i = 1;

int j = 0;
if(str == NULL || nextval == NULL)
return LZM_STRING_STATUS_ERR;
nextval[1] = 0;
while (i str_main[0] + 1)
return LZM_STRING_STATUS_ERR;
nextval = (int *)malloc(str_sub[0]);

if(nextval == NULL)
return LZM_STRING_STATUS_ERR;
nextval_creat(str_sub, nextval);
//根据模式串str_sub,初始化nextval数组while (i<=strlen(str_main) && j<=strlen(str_sub)) 
{
//j==0:代表模式串的第一个字符就和指针i指向的字符不相等；S[i-1]==T[j-1],如果对应位置字符相等，两种情况下，指向当前测试的两个指针下标i和j都向后移
if (j==0 || str_main[i-1] == str_sub[j-1]) 
{
i++;

j++;

}
else
{
j=nextval[j];
//如果测试的两个字符不相等，i不动，j变为当前测试字符串的next值
}
}
if (j > strlen(str_sub)) 
{
//如果条件为真，说明匹配成功
return i-(int)strlen(str_sub);

}
return LZM_STRING_STATUS_ERR;

}/**
 * @namestr_replace
 * @brief删除部分
 * @param
 * @retval 
 * @author lzm
 */
int str_replace(string_t str_s, string_t str_t, string_t str_v)
{
int i = 0;
if(str_s == NULL || str_t == NULL || str_empty(str_v) != LZM_STRING_STATUS_OK)
return LZM_STRING_STATUS_ERR;
do
	{
i = str_kmp_index(str_s, str_t, i);
 /*结果i为从上一个i之后找到的子串T的位置 */
if(i) /*串str_s中存在串str_t */
{
str_delete(str_s, i, str_length(str_t));
 /*删除该串str_t */
str_insert(str_s, str_v, i);
 /*在原串str_t的位置插入串str_v */
i+=str_length(str_v);
 /*在插入的串str_v后面继续查找串str_t */
}
	}
while(i);
	return LZM_STRING_STATUS_OK;

}




		  	

    
    




    
    
    


推荐阅读

           
                  
              
                  如何查询电脑上安装的.net版本，查看电脑net版本 
                
                   
                
              
            

                  
              
                  男人常吃海参会有什么效果 男人备孕吃海参有什么好处 
                
                   
                
              
            

                  
              
                  榴莲和虾一起吃会有什么反应 
                
                   
                
              
            

                  
              
                  《偷偷藏不住》段嘉许真实身世如何 《偷偷藏不住》段嘉许简介 
                
                   
                
              
            

                  
              
                  有限公司董事忠实义务是什么，公司董事的忠实义务 
                
                   
                
              
            

                  
              
                  不能开机充电的机友们注意啦！！！ 
                
                   
                
              
            

                  
              
                  追尾要处罚什么责任 
                
                   
                
              
            

                  
              
                  使用寿命|苹果手机电池可以充多少次？看完它的执行标准，你就知道了 
                
                   
                
              
            

                  
              
                  藏青盐可以长期吃吗 
                
                   
                
              
            

                  
              
                  洋葱裤是什么意思 
                
                   
                
              
            

                  
              
                  岁月可期不负流年啥意思 流年不负岁月可期的意思 
                
                   
                
              
            

                  
              
                  卤水点豆腐一物降一物什么意思 卤水点豆腐一物降一物的含义 
                
                   
                
              
            

                  
              
                  大道至简是什么意思？ 
                
                   
                
              
            

                  
              
                  预算15W落地,轿车有哪些合适的？ 
                
                   
                
              
            

                  
              
                  苹果14序列号查询产地，通过苹果手机序号能查出是在哪个城市买的吗 
                
                   
                
              
            

                  
              
                  西藏大学录取分数线2022考研是多少分 西藏大学录取分数线2022 
                
                   
                
              
            

                  
              
                  怎样制作手工鞭炮 
                
                   
                
              
            

                  
              
                  unixodbc|unixODBC使用经验分享 
                
                   
                
              
            

                  
              
                  奈奈生是什么梗奈奈生是什么意思 
                
                   
                
              
            

                  
              
                  ADAMoracle预言机如何保证传输信息的可靠性 
                
                   
                
              
            

          

JAVA（抽象类与接口的区别&重载与重写&内存泄漏） 
 宽容谁 
 我要做大厨 
 增长黑客的海盗法则 
 画画吗（） 
 2019-02-13——今天谈梦想（） 
 远去的风筝 
 三十年后的广场舞大爷 
 叙述作文 
 20190302|20190302 复盘翻盘