【白话数据结构 08】字符串 —— 字符串匹配算法(面试高频考点!)

文章目录一、白话字符串1.1 什么是字符串1.2 字符串的存储结构二、字符串的增删查操作2.1 新增操作2.2 删除操作2.3 查找操作三、字符串匹配算法3.1 案例13.2 案例2四、相关推荐

一、白话字符串
1.1 什么是字符串

字符串是由 n 个字符组成的一个有序整体( 其中,n >= 0 )。例如,s = “AI Jun” ,s 代表这个串的串名,AI Jun 是串的值。这里的双引号不是串的值,作用只是为了将串和其他结构区分开。

在实际操作中,我们经常会用到一些特殊的字符串:

空串,指含有零个字符的串。例如,s = ” ”
空格串,只包含空格的串。它和空串是不一样的,空格串中是有内容的,只不过包含的是空格,且空格串中可以包含多个空格。例如,s = ” “,就是包含了 2 个空格的字符串。
子串,串中任意连续字符组成的字符串叫作该串的子串。

1.2 字符串的存储结构

字符串的存储结构与线性表相同,也有顺序存储和链式存储两种。

字符串的顺序存储结构,是用一组地址连续的存储单元来存储串中的字符序列,一般是用定长数组来实现。有些语言会在串值后面加一个不计入串长度的结束标记符,比如 \0 来表示串值的终结。
字符串的链式存储结构,与线性表是相似的,但由于串结构的特殊性(结构中的每个元素数据都是一个字符),如果也简单地将每个链结点存储为一个字符,就会造成很大的空间浪费。因此,一个结点可以考虑存放多个字符,如果最后一个结点未被占满时,可以使用 “#” 或其他非串值字符补全。如下图所示:

【白话数据结构 08】字符串 —— 字符串匹配算法(面试高频考点!)
在链式存储中,每个结点设置字符数量的多少,与串的长度、可以占用的存储空间以及程序实现的功能相关:

如果字符串中包含的数据量很大,但是可用的存储空间有限,那么就需要提高空间利用率,相应地减少结点数量。
而如果程序中需要大量地插入或者删除数据,应该相应地增加节点数,这样方便增删操作。

总的来说,串的链式存储结构在连接串与串操作时有一定的方便。但是更常用的还是字符串的顺序存储结构,因为它更灵活,与数组相似,可直接通过索引获取元素。

二、字符串的增删查操作

字符串问题中考察更多的是查找子串的位置、替换等操作。下来我们以顺序存储为例,详细介绍一下字符串对于另一个字符串的增删查操作。

2.1 新增操作

字符串的新增操作和数组非常相似,也有两种情况:(假设 s1=“123”, s2=“abc”)

在字符串末尾新增,时间复杂度是O(1)。比如,s1 的最后插入 s2,也叫作字符串的连接,最终得到”123abc”。
在字符串中间位置新增,时间复杂度是O(n)。比如,在s1的1和2之前新增s2得到“1abc23”。

2.2 删除操作

字符串的删除操作和数组同样非常相似,也有两种情况:

删除字符串末尾元素时,不涉及字符的挪位,所以时间复杂度是O(1)。
牵涉删除字符串后字符的挪移操作,那么时间复杂度是 O(n)。

2.3 查找操作

一般而言,只是根据索引值进行一次查找,时间复杂度是O(1)。
更为常见的考点是查找子串是否在字符串中出现过,这类问题也被称作子串查找或字符串匹配。具体的时间复杂度要看情况而定。接下来我们来重点分析。

三、字符串匹配算法
3.1 案例1

题目如下:

字符串 s = "goodgoogle",判断字符串 t = "google" 在 s 中是否存在。

题目分析:

首先,我们来定义两个概念,主串和模式串。我们在字符串 A 中查找字符串 B,则 A 就是主串,B 就是模式串。我们把主串的长度记为 n,模式串长度记为 m。由于是在主串中查找模式串,因此,主串的长度肯定比模式串长,n>m。因此,字符串匹配算法的时间复杂度就是 n 和 m 的函数。

算法流程:

假设要从主串 s = “goodgoogle” 中找到 t = “google” 子串。根据我们的思考逻辑,则有:

首先,我们从主串 s 第 1 位开始,判断 s 的第 1 个字符是否与 t 的第 1 个字符相等。
如果不相等,则继续判断主串的第 2 个字符是否与 t 的第1 个字符相等。直到在 s 中找到与 t 第一个字符相等的字符时,然后开始判断它之后的字符是否仍然与 t 的后续字符相等。
如果持续相等直到 t 的最后一个字符,则匹配成功。
如果发现一个不等的字符,则重新回到前面的步骤中,查找 s 中是否有字符与 t 的第一个字符相等。
如下图所示,s 的第1 个字符和 t 的第 1 个字符相等,则开始匹配后续。直到发现前三个字母都匹配成功,但 s 的第 4 个字母匹配失败,则回到主串继续寻找和 t 的第一个字符相等的字符。这时我们发现主串 s 第 5 位开始相等,并且随后的 6 个字母全匹配成功,则找到结果。
【白话数据结构 08】字符串 —— 字符串匹配算法(面试高频考点!)
C++实现如下:

#include<iostream>
#include<string>

using namespace std;

int main()
{
string s = "goodgoogle";
string t = "google";
int isfind = 0;

for(int i=0; i<s.length() - t.length() + 1; i++)
{
if(s[i] == t[0])
{
int findIndex = 0;

for(int j=0; j<t.length();j++)
{
if(s[i+j] != t[j])
break;
findIndex = j;
}

if(findIndex == t.length()-1)
isfind = 1;
}

}
cout<<isfind<<endl;
return 0;
}

这种匹配算法需要从主串中找到跟模式串的第 1 个字符相等的位置,然后再去匹配后续字符是否与模式串相等。显然,从实现的角度来看,需要两层的循环。第一层循环,去查找第一个字符相等的位置,第二层循环基于此去匹配后续字符是否相等。因此,这种匹配算法的时间复杂度为 O(nm)。

3.2 案例2

题目如下:

查找出两个字符串的最大公共子串。
假设有且仅有 1 个最大公共子串。比如,输入 a = "13452439", b = "123456"。
由于字符串 "345" 同时在 a 和 b 中出现,且是同时出现在 a 和 b 中的最长子串。因此输出 "345"。

算法分析:

这是一道求最大公共子串的题,核心思想还是字符串匹配。

假设字符串 a 的长度为 n,字符串 b 的长度为 m,可见时间复杂度是 n 和 m 的函数。具体算法实现过程如下:

首先,你需要对于字符串 a 和 b 找到第一个共同出现的字符,这跟前面讲到的匹配算法在主串中查找第一个模式串字符一样。
然后,一旦找到了第一个匹配的字符之后,就可以同时在 a 和 b 中继续匹配它后续的字符是否相等。这样 a 和 b 中每个互相匹配的字串都会被访问一遍。全局还要维护一个最长子串及其长度的变量,就可以完成了。

C++实现如下:

#include<iostream>
#include<string>

using namespace std;

int main()
{
string a = "13452439";
string b = "123456";
int maxLength=0;
string maxString;
for(int i=0; i<a.length(); i++)
{
for(int j=0; j<b.length(); j++)
{
if(a[i]==b[j])
{
for(int m=i, n=j; m<a.length()&&n<b.length(); m++,n++)
{
if(a[m] != b[n])
break;
if(maxLength<m-i+1)
{
maxLength = m-i+1;
maxString = a.substr(i, maxLength);
}
}
}
}
}

cout<<maxString<<endl;
return 0;
}

从代码结构来看,第一步需要两层的循环去查找共同出现的字符,这就是 O(nm)。一旦找到了共同出现的字符之后,还需要再继续查找共同出现的字符串,这也就是又嵌套了一层循环。可见最终的时间复杂度是 O(nmm),即 O(nm²)。

四、相关推荐

【C++养成计划】深入数组和字符串(Day8)

【C++养成计划】动态数组 —— 快速上手 STL vector 类(Day14)

【白话数据结构 07】数组 —— 数组的基本操作( 增删查与时间复杂度的关系!)

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【白话数据结构 08】字符串 —— 字符串匹配算法(面试高频考点!)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【白话数据结构 08】字符串 —— 字符串匹配算法(面试高频考点!)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏