字符串匹配

2024-03-26 07:59:46

一、BF算法

Brute-Force简称BF算法，也称单匹配算法。采用穷举的思路。BF是暴力的意思。

算法思路：从T的每一个字符开始依次与P的字符进行匹配。

字符串匹配

BF算法匹配过程：

字符串匹配

【代码实现】

分析：

要完成对于所有字符的匹配工作，可以遍历母串，并逐个与子串比较，若相同，则字串匹配位后移，若不成功，回溯归零（i = i - j + 1和 j = 0），当匹配成功长度等于字串长度，返回结果.

【参考代码】

#include<iostream>
#include<string>
using namespace std;

int BF(string a, string b)
{   int i= 0, j = 0;
    while(i < a.length() && j < b.length())
    {
        if(a[i] == b[j])// 匹配成功，同时移动
        {
            i ++;
            j ++;
        }
        else // 匹配不成功：回溯
        {
            i = i - j + 1;
            j = 0;
        } 
    }
    
    if(j == b.length()) return i - j; // b字符比较完毕，返回位置 
    else return -1;
   
}

int main(){
    string s1, s2;
    cin>> s1 >> s2;
    cout<<BF(s1,s2); // P 在 T 中的起始位置 
    return 0;
}

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int BF(string a, string b)
{   int i = 0, j = 0; // i别忘了也要初始化
    while(i < a.length() && j < b.length())
    {
        if(a[i] == b[j])// 匹配成功，同时移动
        {
            i ++;
            j ++;
        }
        else // 匹配不成功：回溯
        {
            i = i - j + 1;
            j = 0;
        } 
    }
    
    if(j == b.length()) return i - j; // b字符比较完毕，返回位置 
    else return -1;
   
}

int main()
{
    
    int t;
    cin>>t;
    while(t -- )
    {
        string a,b;
        cin>>a>>b;
        string b2 = b;
        reverse(b2.begin(),b2.end());
        string c = b + b2;
        cout<<BF(a,c);
        
    }
    
    return 0;
}

【时间复杂度分析】

假设目标串规模为n，模式串规模为m

最好：O(m)

最坏：最坏的情况是每遍比较都在最后出现不等，即没变最多比较m次，最多比较n-m+1遍。

总的比较次数最多为m(n-m+1)，因此BF算法的时间复杂度为O(mn)。

二、KMP算法

【KMP有什么用】

KMP主要应用在字符串匹配上。

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

为了解决BF算法每次不匹配 j都要回溯到起始位置问题，引入KMP算法

【kMp实现】

KMP具体代码实现有两种一种是next[]数组一种是prefix[]数组，其实用哪一种都可以，使用prefix就是使用前缀表（上图示）。使用next其实放的也是前缀表，只不过是在前缀表的基础上进行了一些调整（如后移一位或者统一减一）——初始位置变成 -1。上面两种数组统称next[]数组当遇到冲突的时候next[]数组方式告诉我们要回退（回溯）到哪里——（就不必要每次都要回到起点了）

【前缀表】

前缀表有什么作用呢？

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

要求前缀表就先要知道什么是前缀什么是后缀：

  • 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

  • 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

字符串匹配

可以看出，文本串中第六个字符b 和 模式串的第六个字符f，不匹配了。如果暴力匹配，会发现不匹配，此时就要从头匹配了。

但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配。

前缀表是如何记录的呢？

首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，在重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

为什么一定要用前缀表呢？

前缀表告诉我们 上次匹配的位置，并跳过去！

回顾一下，刚刚匹配的过程在下标5的地方，遇到不匹配，模式串j + 1指向了f，如图：
字符串匹配

然后就找到了下标2，指向第二个a，继续匹配（p[j + 1] 与 s[i]）：如图：
字符串匹配

以下这句话，对于理解为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配 非常重要！

下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了。

所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

前缀表的计算：理解定义就知道怎么判断啦

理解i与j（不匹配j跳转后）：

字符串匹配

i ：指向后缀末尾的位置（上例指向b）

j： 指向前缀末尾的位置、还代表着下标i之前（包括i）的字串的最长相等前后缀长度（上例为2）

next考虑的是所有非平凡前缀和后缀，即考虑的前缀和后缀都不是整个原串，至少要比原串短一个字符，所以i要从第二个字符开始枚举

模板

个人习惯下标是从1开始的

匹配过程：

文本串(S串)：i从1开始（初始输入时下标是从1开始的）

模式串(P串)：j从0开始，但实际匹配的是j + 1

试图与S[i]匹配的是P[j + 1] (1~j位置的串就是前缀)：

匹配成功则i、j都移动;

匹配不成功：while(j && s[i] != p[j + 1]) j = ne[j]：匹配不成功则j回退到next[j](前缀表)直到S[i]与P[j + 1]匹配为止，或者j为0（退无可退）循环截止

当 j = 模式串的长度时，匹配成功

求next[]数组：

求ne过程和匹配过程完全类似：

模式串i从2开始，i = 1时只有一个数不存在前后缀，即next[1] = 0，故不用计算

j初始化为0，但比较的是p[i] 与 p[j + 1]

while (j && p[i] != p[j + 1]) j = ne[j];当不匹配时j回退到next[j]的位置（退而求其次，不断尝试直到ne[j]的下一个位置匹配成功，ne[ne[j]]）...(j递归回溯求解的过程)，成功之后i、j往后走一步——最终j就是该位置的最长相等公共前后缀了

记录下模式串每一位置上的ne结果：ne[i] = j

循环往复

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

字符串匹配

【acwing KMP字符串】

给定一个模式串 SS，以及一个模板串 PP，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串 PP 在模式串 SS 中多次作为子串出现。

求出模板串 PP 在模式串 SS 中所有出现的位置的起始下标。

输入格式

第一行输入整数 NN，表示字符串 PP 的长度。

第二行输入字符串 PP。

第三行输入整数 MM，表示字符串 SS 的长度。

第四行输入字符串 SS。

输出格式

共一行，输出所有出现位置的起始下标（下标从 00 开始计数），整数之间用空格隔开。

数据范围

1≤N≤1051≤N≤105
1≤M≤1061≤M≤106

输入样例：

3
aba
5
ababa

输出样例：

0 2

【参考代码】

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1e7 + 10;

int ne[N];
char p[N], s[N];

int n, m;

int main()
{
    cin>> n >> p + 1>> m >> s + 1;
    
    // 求ne[]
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }
    
    // 匹配过程:利用ne数组进行模式匹配
    for(int i = 1, j = 0; i <= m; i++)
    {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j ++;
        // 匹配成功
        if( j == n)
        {
            j = ne[j];// 寻找p在s中的下一次出现的位置，利用ne数组优化时间复杂度
            cout<<i - n<<" ";
        }
    }
    
    return 0;
}

匹配成功后： j = ne[j];

因为匹配成功后，p[j + 1]相当于是空字符，一定不匹配s[]中的任何字符，所以可以更新一次j；又或者是p串比在s串中多次出现，你还要继续匹配寻找起始位置

因为p[n + 1] == '\0'，它和s[]中的任何一个字符都不匹配，所以这里写不写都可以。但建议写上，避免以后出现边界问题

cin >> n >> p + 1 >> m >> s + 1

这样读入字符串的下标就从1开始！

三、C++ string中的find()函数

C++ string中的find()函数,通常会用来判断母串中有无某一子串或者字符，匹配的实现原理其实就是KMP算法

#include<iostream>
#include<string>

using namespace std;

int main()
{
    string s1, s2, s3, s4;
    s1 = "ab";
    s2 = "acabdef";
    
    s3 = "cef";
    s4 = "def";
    //1. string中find()返回子窜在母串中的的起始位置（下标记录）
    int t = s2.find(s1); // 返回子窜在母串中的的起始位置 t = 2
    cout<<t;
    
    
    //2. 如果没有找到，那么会返回一个特别的标记npos(也可以理解为-1)。（返回值可以看成是一个int型的数）
    if(s2.find(s3) == -1) cout<<"NO"<<endl;
    else cout<<"YES"<<endl; //结果： NO
    
    if(s2.find(s4) == -1) cout<<"NO"<<endl;
    else cout<<"YES"<<endl; //结果： YES
    
    
    
    return 0;
}
上一篇：“21天好习惯”第一期–1


下一篇：离线赛总结1