KMP字符串匹配算法

发表于 2021-11-23 更新于 2022-11-03 分类于 acwing算法基础课笔记 Artalk： loading...

kmp算法

kmp算法，主串扫描指针不后退

算法思路

acwing 831. kmp字符串

暴力枚举如何做
如何优化

暴力做法

双层循环，遍历模式串 $\textit{S}$ 和模板串 $\textit{P}$

// S[N] p[M]
for (int i = 1; i <= n; ++ i) {
    // 每一个i代表一个匹配开始点
    int _i = i, j = 0;
    // _i接替扫描任务
    while (j <= m) {
        if (s[_i] != p[j]) break;
        _i++;
        j++;
    }
    // j指向了m，说明主串s 从<当前匹配开始点>开始 和 p串匹配上了
    if (j == m) return true;
}

假设匹配到图中绿线处，失配。若按照暴力匹配的思路，当前模式串 $S$ 的扫描指针会指向下一个匹配开始点（会后退），模板串 $P$ 则会回退到起始处，重新进行匹配。

举个🌰，主串为s="a"

问题：如何利用已经获得的信息，减少重复工作？

考虑，模版串 $\textit P$ 最多向后移动到什么位置，可以继续匹配

这个值，只和模板串 $\textit P$ 有关。（对 $\textit P$ 进行预处理）

即：以某点为终点的后缀，和前缀相等，这个相等的前/后缀的长度最大值

关于next数组的含义，将 $next[i]$ 看作一个集合：

集合：和以 $1$ 开始的前缀相同的，终点为 $i$ 的后缀。
属性：最大的长度

用下标来表示，假设 $next[i] = j$

其含义为： $p[1 \dots j] = p[i-j+1 \dots i]$

据此，可以使得模式串 $\textit S$ 在匹配过程中不用后退

以下的 $i$ 和 $j$ 和上一节的含义不同，分别指模式串和模板串的扫描指针。

假设，主串（模式串） $S$ 扫描到 $i$ ，失配（ $s[i] != p[j+1]$ ），而 $i-1$ 之前的均已经匹配

此时要移动模板串 $\textit P$ 向前移动，将模板串的指针指向 $\textit next[j]$ 即可

然后循环此过程，直到匹配，或者 $\textit j$ 退到起点

代码

#include <iostream>

using namespace std;
// P串的长度为N 
// S串的长度为M
const int N = 100010, M = 1000010;

int n, m;
int ne[N]; // next数组
char s[M], p[N];

int main()
{
    // 下标从1开始 ： p+1 s+1
    cin >> n >> p + 1 >> m >> s + 1;
    // 注意：在此代码中 默认s[i] 和 p[j+1]进行匹配
    
    // 求next数组
    // 实际上求 最长 相等前后缀，这样能保证j做的是 最小 移动
    for (int i = 2, j = 0; i <= n; i ++ )
    {    
        // next[1] = 0;所以从i=2开始
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        // 只要j没有退回起点 并且 当前位置失配
        while (j && s[i] != p[j + 1]) j = ne[j];
        // 退出以上while循环有两种可能：1、j已经退到起点了 2、已经匹配了
        if (s[i] == p[j + 1]) j ++ ; // 则j指针向前移动一位
        if (j == n) 
        {
            // j == n 说明匹配成功
            printf("%d ", i - n); 
            // 之所以没有+1是因为 此代码中下标从1开始，而题目要求输出的下标是从0开始的
            j = ne[j];
        }
    }

    return 0;
}

求解next数组简单举例

匹配过程举例

匹配到 $i = 7$ 和 $j+1=7$ 时，失配， $j$ 跳到 $next[6]$ ， $j$ 更新为 4

后记

更新@2022年11月 3日星期四 18时08分26秒 CST

本文之前的思路，字符串下标是从1开始的，前缀长度为几，前缀的右端下标就是几

$next[j]$ 数组的含义，是模式串 $p[1,j]$ 的前后缀相等的长度，因此每一轮主串 $s$ 的第 $i$ 个字符和模式串 $p$ 的第 $j+1$ 字符进行比较

一旦失配，直接移动 $j$ 到和 已经匹配的后缀 相同的前缀右端，接着比较匹配的下一位（j+1）即可

如果字符串的下标从0开始呢？

每一轮比较 $s[i]$ 和 $p[j]$

并且需要稍微改造一下 $next$ 数组的含义， $next[j]$ 表示模式串 $p[0,j$ - $1]$ （不包含失配的下标为j的字符）的前后缀相等的长度

由于下标从 0 开始，这个长度直接就是前缀匹配部分下一位的下标

代码示意

注意：next数组会多一位

int[] getNextArray(String p) {
    if (p.length() == 0) return new int[]{};
    int[] next = new int[p.length() + 1]; // next[m] 表示 p[0,m-1] 即完整模式串的前后缀相等的长度
    for (int i = 1, j = 0; i < p.length(); ++i) {
        while (j > 0 && p.charAt(i) != p.charAt(j)) j = next[j];
        if (p.charAt(i) == p.charAt(j)) j++;
        next[i + 1] = j;
    }
    return next;
}
int kmp(String s, String p) {
    if (s.length() == 0 || p.length() == 0) return -1;
    int[] next = getNextArray(p);
    for (int i = 0, j = 0; i < s.length(); ++i) {
        while (j > 0 && s.charAt(i) != p.charAt(j)) j = next[j];
        if (s.charAt(i) == p.charAt(j)) j++;
        if (j == p.length()) {
            /**
            匹配成功
            code here
            **/
            j = next[j];
        }
    }
    return -1;
}

完整代码

831. KMP字符串

import java.io.*;

class Main {
    static final int N = 100010;
    static final int M = 1000010;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] next = new int[N];
    static char[] s = new char[M];
    static char[] p = new char[N];
    public static void main(String[] args) throws Exception {
        int n = Integer.parseInt(reader.readLine());
        String pstring = reader.readLine();
        int m = Integer.parseInt(reader.readLine());
        String sstring = reader.readLine();
        for (int i = 0; i < m; ++i) s[i] = sstring.charAt(i);
        for (int j = 0; j < n; ++j) p[j] = pstring.charAt(j);
        
        next[0] = next[1] = 0;
        for (int i = 1, j = 0; i < n; ++i) {
            while (j > 0 && p[i] != p[j]) j = next[j];
            if (p[i] == p[j]) j++;
            next[i + 1] = j;
        }
        for (int i = 0, j = 0; i < m; ++i) {
            while (j > 0 && s[i] != p[j]) j = next[j];
            if (s[i] == p[j]) j++;
            if (j == n) {
                log.write(Integer.toString(i - j + 1) + " ");
                j = next[j];
            }
        }
        
        log.flush();
        reader.close();
        log.close();
    }
}