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

方法二：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开始的匹配子串的首字母下标
            printf("%d ", i - m); //(若从1开始，加1)
            j = nex[j];            //再次继续匹配
        }
    }

    return 0;
}

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

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