字符串匹配算法(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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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);
    
}

方法二:KMP算法(最长可匹配前后缀子串算法)

讲解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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开始的匹配子串的首字母下标
            printf("%d ", i - m); //(若从1开始,加1)
            j = nex[j];            //再次继续匹配
        }
    }

    return 0;
}
Scroll to Top