谈及字符匹配算法,不得不提的就是KMP算法,效率高但是复杂。而这篇借鉴动态规划的思想,基于DFA来解决字符串匹配问题

算法代码

import java.util.*;

public class KMP {
    private int[][] dp;
    private String pat;

    public void KMP(String pat) {
        this.pat = pat;
        int M = pat.length();
        // dp[状态][字符] = 下个状态 
        //为了能够在一个字符串完全匹配之后仍然可以匹配随后的字符串,需要M+1个一维数组,表示状态的转换。
        dp = new int[M+1][256]; 
        // 状态数组初始化,dp[0]默认初始化为0,仅匹配模式串第一个字符会引起状态改变
        dp[0][pat.charAt(0)] = 1;
        // 影子状态 X 初始为 0,用于判断状态回退
        int X = 0;
        // 构建状态转移图
        for (int j = 1; j <= M; j++) {
            for (int c = 0; c < 256; c++)
                dp[j][c] = dp[X][c];
            if(j != M){ //状态非最终状态时更新影子状态以及造成状态改变的字符
                dp[j][pat.charAt(j)] = j + 1;
                // 更新影子状态
                X = dp[X][pat.charAt(j)];
            }
        }
    }

    public int[] search(String txt) {
        int M = pat.length();
        int N = txt.length();
        List<Integer> res = new LinkedList<>();
        // pat 的初始态为 0
        int j = 0;
        for (int i = 0; i < N; i++) {
            // 计算 pat 的下一个状态
            j = dp[j][txt.charAt(i)];
            // 到达终止态,返回结果
            if (j == M){
                res.add(i-M+1);
            }
        }
        // 没到达终止态,匹配失败
        int[] result = new int[res.size()];
        for(int i=0;i<res.size();i++){
            result[i] = res.get(i);
        }

        return result;
    }

    public static void main(String[] args){
        String txt = "hello keith, my name is keith, goodbye keith.";
        String pat = "keith";
        KMP kmptester = new KMP(pat);
        int[] p = kmptester.search(txt);
        for(int i:p){
            System.out.println(i);
        }

    }
}

关于状态数组(int[][] dp)的生成

状态数组的产生与文本串无关,只与模式串有关,同一模式串的状态转移数组相同,下图以“ababcb”为例。

dfa展示
dfa展示

for (int j = 1; j <= M; j++) {
            for (int c = 0; c < 256; c++)
                dp[j][c] = dp[X][c];
            if(j != M){ //状态非最终状态时更新影子状态以及造成状态改变的字符
                dp[j][pat.charAt(j)] = j + 1;
                // 更新影子状态
                X = dp[X][pat.charAt(j)];
            }
        }

依次遍历模式串,将影子状态数组赋值给该状态数组,若该状态不是终止状态,则根据第J个字符更新该状态数组,使之转移到正确的状态。

分析

该算法是使用一个二维数组 dp 以状态转移的角度解决字符匹配问题,但空间复杂度仍然是 O(256M) = O(M)。

pat 匹配 txt 的过程中,只要明确了「当前处在哪个状态」和「遇到的字符是什么」这两个问题,就可以确定应该转移到哪个状态(推进或回退)。这也是动态规划问题普遍需要清晰的两个问题。

对于一个模式串 pat,其总共就有 M 个状态,对于 ASCII 字符,总共不会超过 256 种。所以我们就构造一个数组 dp[M][256] 来包含所有情况,并且明确 dp 数组的含义:

dp[j][c] = next 表示,当前是状态 j,遇到了字符 c,应该转移到状态 next

对于如何构建这个 dp 数组,需要一个辅助状态 X,它永远比当前状态 j 落后一个状态,拥有和 j 最长的相同前缀,我们给它起了个名字叫「影子状态」,也可以称作前缀状态。

在构建当前状态 j 的转移方向时,只有字符 pat[j] 才能使状态推进(dp[j][pat[j]] = j+1);而对于其他字符只能进行状态回退,应该去请教影子状态 X 应该回退到哪里(dp[j][other] = dp[X][other],其中 other 是除了 pat[j] 之外所有字符)。

对于影子状态 X,我们把它初始化为 0,并且随着 j 的前进进行更新,更新的方式和 search 过程更新 j 的过程非常相似(X = dp[X][pat[j]])。

KMP 算法也就是动态规划那点事,我们的公众号文章目录有一系列专门讲动态规划的,而且都是按照一套框架来的,无非就是描述问题逻辑,明确 dp 数组含义,定义 base case 这点破事。希望这篇文章能让大家对动态规划有更深的理解。