【算法与数据结构 08】字符串 —— 字符串匹配算法（面试高频考点！）

今天药忘吃喽~ 2022-12-03 08:52 165阅读 0赞

### 文章目录 ###

*   *  一、白话字符串
     *   *  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 来表示串值的终结。
 *  字符串的**链式存储结构**，与线性表是相似的，但由于串结构的特殊性（结构中的每个元素数据都是一个字符），如果也简单地将每个链结点存储为一个字符，就会造成很大的空间浪费。因此，一个结点可以考虑存放多个字符，如果最后一个结点未被占满时，可以使用 “\#” 或其他非串值字符补全。如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center]  
在链式存储中，每个结点设置字符数量的多少，与串的长度、可以占用的存储空间以及程序实现的功能相关：

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

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

--------------------

## 二、字符串的增删查操作 ##

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

### 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 个字母全匹配成功，则找到结果。  
    ![在这里插入图片描述][20200902165705227.gif_pic_center]  
    **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_Day8]

[【C++养成计划】动态数组 —— 快速上手 STL vector 类（Day14）][C_ _ _ STL vector _Day14]

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/127439fc0d9f45549ebb9c8aee1331b1.png
[20200902165705227.gif_pic_center]: /images/20221123/bb6f8fdca0584e6c9b61aab51bb9bbb9.png
[C_Day8]: https://blog.csdn.net/wjinjie/article/details/106077362
[C_ _ _ STL vector _Day14]: https://blog.csdn.net/wjinjie/article/details/108381370
[07_ _ _]: https://blog.csdn.net/wjinjie/article/details/108360908