KMP

hotarugali

发布于 2022-03-02 20:37:04

6510

1. 简介

KMP 算法是一种优秀的字符串模式匹配算法，相对于暴力匹配方法来说，其改进在于：每当一趟匹配过程出现字符比较不相等时，不需回溯主串的 iii 指针，而是利用已经得到的「部分匹配」的结果将模式串向右「滑动」尽可能远的一段距离后（即回溯模式串的 jjj 指针），继续进行比较。

2. 实现

设模式串为p_1 p_2 \cdots p_m，主串为s_1 s_2 \cdots s_n。
定义失配数组 next[j]表示当模式串中第 j 个字符与主串中相应字符失配时，在模式串中需要重新和主串中该字符进行比较的模式串字符的位置。

假设从主串第 pos个字符开始和模式串匹配，此时主串中第i(pos \leq i)个字符和模式串的第j 个字符比较，且 s_i \ne p_j，说明从主串第 pos 个字符开始匹配无法找到模式串子串，因此需要将 pos向右「滑动」（即增大主串开始匹配字符的位置）。
而增大主串开始匹配字符的位置可以通过将模式串向右「滑动」实现。如果此时存在最大的 k 使得 p_0 \cdots p_{k-1} = p_{j-k} \cdots p_{j-1} 且 p_k \ne p_j ，则可以将模式串向右「滑动」使得模式串第 k 个字符对应到第 j个字符，即模式串整体向右滑动了 j-k个字符。

设k = max\{u | 0 \lt u \lt j \bigwedge p_0 \cdots p_{u-1} = p_{j-u} \cdots p_{j-1}\} ，则失配数组的计算公式如下：

\begin{array}{c} next[j] = \begin{cases} -1 & j = 0 \\ k & if \ p_{k} \ne p_{j} \\ next[k] & if \ p_{k} = p_{j} \end{cases} \end{array}

计算失配数组时间复杂度 O(m)，主串与模式串匹配时间复杂度 O(n)，故 KMP 算法总的时间复杂度为 O(n+m) 。

3. 模板

#include <bits/stdc++.h>
using namespace std;

#ifndef _KMP_
#define _KMP_
#define ll int
#define MAXN 1000005
#define MAXM 1000005

// KMP 算法
struct KMP {
    // 失配数组
    // next[j] 表示当模式中第 j 个字符与主串字符失配时
    // 模式串中失配位置需要滑动到的位置
    ll next[MAXM];   
    vector <ll> match;          
    KMP() {}
    // 计算失配数组
    void getNext(char *pattern, ll m) {
        // pattern 模式串
        next[0] = -1;
        ll i = 0, j = -1;
        while(i < m) {
            if(!(~j) || pattern[i] == pattern[j]) {
                ++i, ++j;
                if(pattern[i] != pattern[j])    next[i] = j;
                else    next[i] = next[j];
            } else {
                j = next[j];
            }
        }
    }
    // 计算模式串在主串中第 pos 个字符后出现首个匹配的首位置
    ll getIndex(ll pos, char *main, ll n, char *pattern, ll m) {
        ll i = pos, j = 0;
        while(i < n && j < m) {
            if(!(~j) || main[i] == pattern[j]) {
                ++i, ++j;
            } else {
                j = next[j];
            }
        }
        if(j < m) {
            return -1;
        }
        return i - m;
    }
    // 计算模式串在主串中所有匹配的首位置
    void getIndexs(char *main, ll n, char *pattern, ll m) {
        ll i = 0, j = 0;
        while(i < n) {
            if(!(~j) || main[i] == pattern[j]) {
                ++i, ++j;
                if(j == m) {
                    j = next[j];
                    match.push_back(i-m);
                }
            } else {
                j = next[j];
            }
        }
    }
};
#endif

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-09-03，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

KMP

KMP

1. 简介

2. 实现

3. 模板

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐