字符串匹配算法(KMP算法)

适用级别：提高组
难度系数：5

KMP算法是解决在一个字符串中查找另外一个字符串的问题，全名为Knuth-Morris-Prett算法，以三个发明人名字命名。

已知字符串A和字符串B，字符串B是字符串A的子串，计算B在A中第一次出现的位置是，若无法匹配到子串则返回-1，一般我们统一将这里的A称为主串，B称为模式串。
例如：
字符串A ：a b c d e f h
字符串B ： c d e f
则B在A中第一次出现的位置是2

方法一：暴力算法(brute force)

时间复杂度：O(n*m)

#include <iostream>
using namespace std;

int brute_force(const char *s, int n, const char *t,int m){
    //扫描文本串的每一位
    for(int i = 0; i<n; i++){
        bool flag = true;
        //用当前的第i位和模式串向后比较
        for(int j = 0; j<m; j++){
            if(s[i + j] == t[j]) continue;
            flag = false;
            break;
        }
        if(flag) return i;  
    }
    return -1;
}


int main(){
    char c1,c2,s[100],t[10];
    int i=0,j=0;
    while((c1=getchar())!='\n'){
        s[i]=c1;
	 i++;
	}
     while((c2=getchar())!='\n'){
        t[j]=c2;
	 j++;
	}
    
    cout<<brute_force(s,i,t,j);
    
}

方法二：跳跃查找

代码实现：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-20 11:27:08
 * 最后修改: 2025-01-20 20:36:55
 * 文件描述: 当模式字符串为不重复字符时，使用滑动窗口算法
****************************************************************/
#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool hasSubstringMatch(const string& s, const string& t) {
    int n = s.size();
    int m = t.size();

    if (m == 0 || n < m) return false;

    // 遍历主字符串
    for (int i = 0; i <= n - m; ) {
        int j = 0; // t 的索引
        // 比较当前窗口中的字符
        while (j < m && s[i + j] == t[j]) {
            j++;
        }

        // 如果匹配了整个目标字符串
        if (j == m) {
            return true;
        }

        // 跳过不必要的字符比较
        // 当 `s[i + j] != t[j]` 时，检查下一步的位置
        if (j == 0) {
            i++; // 如果第一个字符就不匹配，直接移动到下一个字符
        } else {
            i += j; // 否则跳过已经匹配的部分
        }
    }

    return false;
}

int main() {
    string s = "abdabeabfabc";
    string t = "abc";

    if (hasSubstringMatch(s, t)) {
        cout << "Found matching substring!" << endl;
    } else {
        cout << "No matching substring found." << endl;
    }

    return 0;
}

方法二：KMP算法（最长可匹配前后缀子串算法）

如果模式字符串中有重复的字符，哪么可以采用KMP算法。

1、前缀与后缀的定义
前缀：对于一个字符串，从该字符串的第一个字符开始，到第i个字符结束的子串，就是该字符的一个前缀。
后缀：对于某个字符串，从该字符串的第i个字符开始，到最后一个字符结束，就是该字符串的一个后缀。

2、next数组

next 数组（也称为部分匹配表或失配数组）是核心部分，用于记录模式字符串中最长公共前缀和后缀的长度，以优化匹配过程。
对于子串s，设定next[]数组，next[i]=j表示的意义是以i结束的长度为j的一个后缀与从第一个字符开始的长度为j的前缀是相等的，并且该长度值是所有可能的前缀与后缀相等的长度值中除了自身相等以外的最大值。

例一：对于 P=”ababc”，计算过程如下：

i	P[0:i]	j (前缀末尾)	匹配	next[i]
0	a	0	–	0
1	ab	0	不匹配	0
2	aba	1	匹配	1
3	abab	2	匹配	2
4	ababc	0	不匹配	0

最终结果：next = [0, 0, 1, 2, 0]

例二：字符串s=ababababaabab，该字符串的next数组值如下。

s	a	b	a	b	a	b	a	a	b	a	b
next[]	0	0	1	2	3	4	5	1	2	3	4

下面我们图示KMP算法

代码实现：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2022-08-05 23:43:11
 * 最后修改: 2025-01-22 19:37:20
 * 文件描述: KMP字符串匹配算法
***************************************************************/
#include <iostream>
using namespace std;

const int N = 100010, M = 10010; //N为主串长度，M模式串长度

int n, m;
int nex[M]; //next[]数组，避免和头文件next冲突
char s[N], p[M];  //s为主串， p为模式串

int main(){
    cin >> n >> (s+1)>> m >>(p+1);  //下标从1开始,n是s主串实际长度，m是p模式串实际长度

    //求next[]数组
    for(int i = 2, j = 0; i <= m; i++){
        while(j && p[i] != p[j+1]) j = nex[j];
        if(p[i] == p[j+1]) j++;
        nex[i] = j;
    }
    //匹配操作
    for(int i = 1, j = 0; i <= n; i++)
    {
        while(j && s[i] != p[j+1]) j = nex[j];
        if(s[i] == p[j+1]) j++;
        if(j == m)  //满足匹配条件，打印开头下标, 从0开始
        {
            //匹配完成后的具体操作
            //如：输出以0开始的匹配子串的首字母下标
            cout << i - m << " "; //(若从1开始，加1)
            j = nex[j];            //再次继续匹配
        }
    }

    return 0;
}

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

字符串匹配算法(KMP算法)