文章目录
- 一、白话字符串
- 1.1 什么是字符串
- 1.2 字符串的存储结构
- 二、字符串的增删查操作
- 2.1 新增操作
- 2.2 删除操作
- 2.3 查找操作
- 三、字符串匹配算法
- 3.1 案例1
- 3.2 案例2
- 四、相关推荐
一、白话字符串
1.1 什么是字符串
字符串是由 n 个字符组成的一个有序整体（ 其中，n >= 0 ）。例如，s = “AI Jun” ，s 代表这个串的串名，AI Jun 是串的值。这里的双引号不是串的值，作用只是为了将串和其他结构区分开。
在实际操作中，我们经常会用到一些特殊的字符串：
- 空串，指含有零个字符的串。例如，s = " "
- 空格串，只包含空格的串。它和空串是不一样的，空格串中是有内容的，只不过包含的是空格，且空格串中可以包含多个空格。例如，s = " "，就是包含了 2 个空格的字符串。
- 子串，串中任意连续字符组成的字符串叫作该串的子串。
1.2 字符串的存储结构
字符串的存储结构与线性表相同，也有顺序存储和链式存储两种。
- 字符串的顺序存储结构，是用一组地址连续的存储单元来存储串中的字符序列，一般是用定长数组来实现。有些语言会在串值后面加一个不计入串长度的结束标记符，比如 \0 来表示串值的终结。
- 字符串的链式存储结构，与线性表是相似的，但由于串结构的特殊性（结构中的每个元素数据都是一个字符），如果也简单地将每个链结点存储为一个字符，就会造成很大的空间浪费。因此，一个结点可以考虑存放多个字符，如果最后一个结点未被占满时，可以使用 “#” 或其他非串值字符补全。如下图所示：
在链式存储中，每个结点设置字符数量的多少，与串的长度、可以占用的存储空间以及程序实现的功能相关：
- 如果字符串中包含的数据量很大，但是可用的存储空间有限，那么就需要提高空间利用率，相应地减少结点数量。
- 而如果程序中需要大量地插入或者删除数据，应该相应地增加节点数，这样方便增删操作。
总的来说，串的链式存储结构在连接串与串操作时有一定的方便。但是更常用的还是字符串的顺序存储结构，因为它更灵活，与数组相似，可直接通过索引获取元素。
二、字符串的增删查操作
字符串问题中考察更多的是查找子串的位置、替换等操作。下来我们以顺序存储为例，详细介绍一下字符串对于另一个字符串的增删查操作。
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 个字母全匹配成功，则找到结果。
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】数组 —— 数组的基本操作( 增删查与时间复杂度的关系！)
