C++ 算法学习——1.4 字符串匹配：KMP算法

时间：2024-10-14 13:43:50

基本思想：

KMP算法通过利用模式串自身的信息来避免在文本串中不必要的比较，从而提高匹配的效率。它的核心在于构建一个部分匹配表（也可叫next数组）（也称为失配函数），该表记录了模式串中每个位置对应的最长相同前缀后缀的长度。

实现步骤：

  1. 构建部分匹配表next数组（失配函数表）：

    • 遍历模式串，针对每个位置计算最长相同前缀后缀的长度。
    • 基于这些信息构建部分匹配表。

  2. 匹配过程：

    • 在文本串和模式串上同时移动指针，根据部分匹配表调整模式串的位置。

下面以具体例子示范匹配过程(B站BV1AY4y157yL视频例子） 

首先看看next数组（部分匹配表）有什么用：

 首先从头开始匹配，借助两指针比较具体位置。上述例子中,匹配到第四位发现不对，于是作以下操作：子串指针回到某个位置i(子串以0作索引),这个i是next数组中最后一个匹配到的字符对应的next值（此处是1）。得到如下结果：

后指针继续匹配，重复上述过程直到主串指针到end或匹配成功.

再讲讲next数组如何构建:

其本质是寻找子串中以头到当前字符结尾的字符串最大相同前缀和后缀的长度。比如：

所以最后一个A对应的next数值是3.

大致代码如下：

#include <iostream>
#include <vector>

using namespace std;

// 构建部分匹配表
vector<int> buildPartialMatchTable(string pattern) {
    int m = pattern.size();
    vector<int> partialMatch(m, 0);
    int length = 0;  // 已匹配的长度

    for (int i = 1; i < m; i++) {
        if (pattern[i] == pattern[length]) {
            length++;
            partialMatch[i] = length;
        } else {
            if (length != 0) {
                length = partialMatch[length - 1];
                i--;  // 继续比较当前位置
            }
        }
    }

    return partialMatch;
}

// KMP算法函数
int kmpSearch(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();
    vector<int> partialMatch = buildPartialMatchTable(pattern);

    int i = 0;  // 指向文本串
    int j = 0;  // 指向模式串

    while (i < n) {
        if (text[i] == pattern[j]) {
            if (j == m - 1) {
                // 匹配成功，返回匹配位置
                return i - j;
            }
            i++;
            j++;
        } else {
            if (j > 0) {
                j = partialMatch[j - 1];
            } else {
                i++;
            }
        }
    }

    return -1;  // 没有匹配
}

 

P1. 洛谷p4391 radio transmission

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 构建部分匹配表
vector<int> buildPartialMatchTable(string pattern) {
    int m = pattern.size();
    vector<int> partialMatch(m, 0);
    int length = 0;  // 已匹配的长度

    for (int i = 1; i < m; i++) {
        if (pattern[i] == pattern[length]) {
            length++;
            partialMatch[i] = length;
        } else {
            if (length != 0) {
                length = partialMatch[length - 1];
                i--;  // 继续比较当前位置
            }
        }
    }

    return partialMatch;
}

// KMP算法函数
int kmpSearch(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();
    vector<int> partialMatch = buildPartialMatchTable(pattern);

    int i = 0;  // 指向文本串
    int j = 0;  // 指向模式串

    while (i < n) {
        if (text[i] == pattern[j]) {
            if (j == m - 1) {
                // 匹配成功，返回匹配位置
                return i - j;
            }
            i++;
            j++;
        } else {
            if (j > 0) {
                j = partialMatch[j - 1];
            } else {
                i++;
            }
        }
    }

    return -1;  // 没有匹配
}

int main()
{
    int n;cin>>n;
    string a;cin>>a;
    //string b=a.substr(0,3);//索引为0，长度为3的子串
    vector<int> array=buildPartialMatchTable(a);
    //for(int i=0;i<array.size();i++)
    //{
        //cout<<array[i]<<" ";
    //}
    //cout<<endl;
    cout<<a.length()-array[n-1];
    return 0;
}

相关文章