数据结构(3)—— 串

### 写在前面

关于串,906的考纲内并没有涉及,408中也只提到了模式匹配算法(KMP算法),因此这块的内容会很少,并不会有太多涉及。

一如既往的,上一部分的地址:[数据结构(2)—— 栈与队列](https://www.cnblogs.com/wushenjiang/p/15004139.html)。

### KMP匹配算法

#### 注意点

需要注意的是,代码里求next数组的过程与我们手算的过程是不一样的,因此这里的思路仅做参考。

求next数组的算法流程,可以去看王道书和[KMP算法(快速模式匹配算法)详解以及C语言实现 (biancheng.net)](http://data.biancheng.net/view/13.html)这个网址的讲解,讲的很不错。以我的能力无法叙述很好,就在此借助网络的力量了。

关于手算next数组,可以参考王道2022考研的视频,讲解的很好。

这里的代码使用了C++中定义好的string类型,并且把整体写法偏向了C++风格(实际上也就是多了个namespace的声明和打印方式的改变而已)。

#### 代码

```cpp
/*
 * @Description: KMP算法实现
 * @version: 1.0
 * @Author: Liuge
 * @Date: 2021-07-13 21:20:30
 */

#include<bits/stdc++.h>
using namespace std;

// 求next数组
// 这里的字符串是从0开始存储的,所以需要下标-1
void getNext(string T,int next[]){
    int i=1;
    int j=0;
    next[1] = 0;
    while(i < T.length()){
        if(j == 0 || T[i-1] == T[j-1]){
            ++i;
            ++j;
            next[i] = j;
        }else{
            j = next[j];
        }
    }
}

// KMP算法
int indexKMP(string S,string T,int next[]){
    int i=1;
    int j=1;
    while(i <= S.length() && j <= T.length()){
        if(j == 0 || S[i-1] == T[j-1]){
            ++i;
            ++j;
        }else{
            j = next[j];
        }
    }
    if(j > T.length()){
        return i - T.length();
    }else{
        return 0;
    }
}

// 主函数测试
int main(){
    string a = "ababcabcacbab";
    string b = "cabca";
    int next[100];
    getNext(b,next);
    cout << "子串b在子串a的起始位置为:" << indexKMP(a,b,next);
}

总结

这次实现并不是很难,而且由于考纲的要求比较低,且对代码也没什么要求,读者凑合看看就好。按照王道书上所说,暴力循环来模式匹配的方式时间复杂度其实也没那么不堪,因此也被广泛使用。在实际的项目中更多的是使用别人写好的工具类,可以参考下真正的工程项目是如何实现模式匹配的。

数据结构(3)—— 串

上一篇:rest client 代替postman


下一篇:UParams