标签搜索

目 录CONTENT

文章目录

动态规划之KMP字符匹配算法.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 4 阅读 / 7,949 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

动态规划之KMP字符匹配算法

@[toc]
本文的KMP算法是通过状态机的改进版本,普通的KMP实现方法请点击:👇
https://blog.csdn.net/wolfGuiDao/article/details/108299448

一、问题引入

KMP 算法(Knuth-Morris-Pratt 算法) 是⼀个著名的字符串匹配算法, 效率很⾼, 但是确实有点复杂。

先在开头约定, 本⽂⽤ pat 表⽰模式串, ⻓度为 M , txt 表⽰⽂本串,⻓度为 N 。 KMP 算法是在 txt 中查找⼦串 pat , 如果存在, 返回这个⼦串的起始索引, 否则返回 -1

读者⻅过的 KMP 算法应该是, ⼀波诡异的操作处理 pat 后形成⼀个⼀维的数组 next , 然后根据这个数组经过⼜⼀波复杂操作去匹配 txt 。 时间复杂度 O(N), 空间复杂度 O(M)。

其实它这个 next 数组就相当于 dp 数组, 其中元素的含义跟 pat 的前缀和后缀有关, 判定规则⽐较复杂, 不好理解。 本⽂则⽤⼀个⼆维的 dp 数组(但空间复杂度还是 O(M)) , 重新定义其中元素的含义, 使得代码⻓度⼤⼤减少, 可解释性⼤⼤提⾼。

二、 KMP 算法概述

⾸先还是简单介绍⼀下 KMP 算法和暴⼒匹配算法的不同在哪⾥, 难点在哪⾥, 和动态规划有啥关系。

暴⼒的字符串匹配算法很容易写, 看⼀下它的运⾏逻辑:

// 暴⼒匹配(伪码)
int search(String pat, String txt) {
	int M = pat.length;
	int N = txt.length;
	for (int i = 0; i <= N - M; i++) {
		for (int j = 0; j < M; j++) {
			if (pat[j] != txt[i + j])
				break;
		}
	// pat 全都匹配了
		if (j == M) return i;
	} 
	// txt 中不存在 pat ⼦串
	return -1;
}

对于暴⼒算法, 如果出现不匹配字符, 同时回退 txt 和 pat 的指针, 嵌套 for 循环, 时间复杂度$O(MN)$, 空间复杂度$O(1)$。 最主要的问题是,如果字符串中重复的字符⽐较多, 该算法就显得很蠢。

⽐如 txt = "aaacaaab" pat = "aaab":

很明显, pat 中根本没有字符 c, 根本没必要回退指针 i , 暴⼒解法明显多做了很多不必要的操作

KMP 算法的不同之处在于, 它会花费空间来记录⼀些信息, 在上述情况中就会显得很聪明:

再⽐如类似的 txt = "aaaaaaab" pat = "aaab", 暴⼒解法还会和上⾯那个例⼦⼀样蠢蠢地回退指针 i , ⽽ KMP 算法⼜会耍聪明:

因为 KMP 算法知道字符 b 之前的字符 a 都是匹配的, 所以每次只需要⽐较字符 b 是否被匹配就⾏了。

==KMP 算法永不回退 txt 的指针 i , 不⾛回头路(不会重复扫描txt ) , ⽽是借助 dp 数组中储存的信息把 pat 移到正确的位置继续匹配, 时间复杂度只需 O(N), ⽤空间换时间, 所以我认为它是⼀种动态规划算法==。

KMP 算法的难点在于, 如何计算 dp 数组中的信息? 如何根据这些信息正确地移动 pat 的指针? 这个就需要确定有限状态⾃动机来辅助了, 别怕这种⾼⼤上的⽂学词汇, 其实和动态规划的 dp 数组如出⼀辙, 等你学会了也可以拿这个词去吓唬别⼈。

还有⼀点需要明确的是: ==计算这个 dp 数组, 只和 pat 串有关==意思是说, 只要给我个 pat , 我就能通过这个模式串计算出 dp 数组, 然后你可以给我不同的 txt , 我都不怕, 利⽤这个 dp 数组我都能在 O(N) 时间完成字符串匹配

具体来说, ⽐如上⽂举的两个例⼦:

txt1 = "aaacaaab"
pat = "aaab"
txt2 = "aaaaaaab"
pat = "aaab"

我们的 txt 不同, 但是 pat 是⼀样的, 所以 KMP 算法使⽤的 dp 数组是同⼀个

只不过对于 txt1 的下⾯这个即将出现的未匹配情况:

在这里插入图片描述
dp 数组指⽰ pat 这样移动:

在这里插入图片描述

这个 j 不要理解为索引, 它的含义更准确地说应该是状态(state) ,所以它会出现这个奇怪的位置

⽽对于 txt2 的下⾯这个即将出现的未匹配情况:
在这里插入图片描述

dp 数组指⽰ pat 这样移动:

在这里插入图片描述

明⽩了 dp 数组只和 pat 有关, 那么我们这样设计 KMP 算法就会⽐较漂亮:

public class KMP {
	private int[][] dp;
	private String pat;
	
	public KMP(String pat) {
		this.pat = pat;
		// 通过 pat 构建 dp 数组
		// 需要 O(M) 时间
	} 
	public int search(String txt) {
		// 借助 dp 数组去匹配 txt
		// 需要 O(N) 时间
	}
}

这样, 当我们需要⽤同⼀ pat 去匹配不同 txt 时, 就不需要浪费时间构造 dp 数组了:

KMP kmp = new KMP("aaab");
int pos1 = kmp.search("aaacaaab"); //4
int pos2 = kmp.search("aaaaaaab"); //4

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  •  代码描述:
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> GetNext(string& match)
{
    vector<int> next(match.size() + 1,0);
    next[0] = -1;
    
    int i = 2;
    int k = 0;
    while(i < match.size())
    {
        if(match[i - 1] == match[k])
        {
            next[i] = k + 1;
            k = next[i];
            i++;
        }
        else if(k == -1)
        {
            next[i] = 0;
            i++;
        }
        else 
        {
            k = next[k];
        }
    }
    return next;
}

int main()
{
    string str;
    string match;
    while(getline(cin,str))
    {
        getline(cin,match);
        vector<int> next = GetNext(match);
        
        int flag = 1;
        
        int i = 0;
        int j = 0;
        while(i < str.size())
        {
            if(str[i] == match[j])
            {
                i++;
                j++;
                if(j == match.size())
                {
                    flag = 0;
                    cout<<i - match.size()<<" ";
                    j = next[j];
                }
            }
            else
            {
                j = next[j];
                if(j == -1)
                {
                    j = 0;
                    i++;
                }
            }
        }
        if(flag)
            cout<<-1<<endl;
    }
    return 0;
}

三、 状态机概述

为什么说 KMP 算法和状态机有关呢? 是这样的, 我们可以认为 pat 的匹配就是状态的转移。 ⽐如当 pat = "ABABC":
在这里插入图片描述

如上图, 圆圈内的数字就是状态, 状态 0 是起始状态, 状态 5( pat.length ) 是终⽌状态

开始匹配时 pat 处于起始状态, ⼀旦转移到终⽌状态, 就说明在 txt 中找到了 pat 。 ⽐如说当前处于状态 2, 就说明字符 "AB" 被匹配:

在这里插入图片描述

另外, 处于不同状态时, pat 状态转移的⾏为也不同⽐如说假设现在匹配到了状态 4, 如果遇到字符 A 就应该转移到状态 3, 遇到字符 C 就应该转移到状态 5, 如果遇到字符 B 就应该转移到状态 0

在这里插入图片描述

具体什么意思呢, 我们来⼀个个举例看看。 ⽤变量 j 表⽰指向当前状态的指针, 当前 pat 匹配到了状态 4:

在这里插入图片描述

如果遇到了字符 "A", 根据箭头指⽰, 转移到状态 3 是最聪明的:

在这里插入图片描述

如果遇到了字符 "B", 根据箭头指⽰, 只能转移到状态 0(⼀夜回到解放前) :

在这里插入图片描述

如果遇到了字符 "C", 根据箭头指⽰, 应该转移到终⽌状态 5, 这也就意味着匹配完成:

在这里插入图片描述

当然了, 还可能遇到其他字符, ⽐如 Z, 但是显然应该转移到起始状态 0,因为 pat 中根本都没有字符 Z:
在这里插入图片描述

这⾥为了清晰起⻅, 我们画状态图时就把其他字符转移到状态 0 的箭头省略, 只画 pat 中出现的字符的状态转移:

在这里插入图片描述

好了,上面我们已经逼逼赖赖了那么多,重点来了,KMP 算法最关键的步骤就是构造这个状态转移图

要确定状态转移的⾏为, ==得明确两个变量, ⼀个是当前的匹配状态, 另⼀个是遇到的字符==;确定了这两个变量后, 就可以知道这个情况下应该转移到哪个状态。

为了描述状态转移图, 我们定义⼀个⼆维 dp 数组, 它的含义如下:

dp[j][c] = next
0 <= j < M, 代表当前的状态
0 <= c < 256, 代表遇到的字符(ASCII 码)
0 <= next <= M, 代表下⼀个状态
dp[4]['A'] = 3 表⽰:
当前是状态 4, 如果遇到字符 A,
pat 应该转移到状态 3

dp[1]['B'] = 2 表⽰:
当前是状态 1, 如果遇到字符 B,
pat 应该转移到状态 2

根据我们这个 dp 数组的定义和刚才状态转移的过程, 我们可以先写出 KMP算法的 search 函数代码:

public int search(String txt) {
	int M = pat.length();
	int N = txt.length();
	// pat 的初始态为 0
	int j = 0;
	for (int i = 0; i < N; i++) 
	{
		// 当前是状态 j, 遇到字符 txt[i],
		// pat 应该转移到哪个状态?
		j = dp[j][txt.charAt(i)];
		// 如果达到终⽌态, 返回匹配开头的索引
		if (j == M) 
			return i - M + 1;
	} 
	// 没到达终⽌态, 匹配失败
	return -1;
}

到这⾥, 应该还是很好理解的吧, dp 数组就是我们刚才画的那幅状态转移图,

四、 构建状态转移图

重重重点又来了!如何构建状态转移图???

要确定状态转移的⾏为, ==必须明确两个变量, ⼀个是当前的
匹配状态, 另⼀个是遇到的字符==
, ⽽且我们已经根据这个逻辑确定了 dp数组的含义, 那么构造 dp 数组的框架就是这样:

for 0 <= j < M: # 状态
	for 0 <= c < 256: # 字符
		dp[j][c] = next

这个 next 状态应该怎么求呢? 显然, 如果遇到的字符 c 和 pat[j] 匹配的话, 状态就应该向前推进⼀个, 也就是说 next = j + 1 , 我们不妨称这种情况为状态推进:

在这里插入图片描述

如果字符 c 和 pat[j] 不匹配的话, 状态就要回退(或者原地不动) , 我们不妨称这种情况为状态重启

在这里插入图片描述

那么, 如何得知在哪个状态重启呢? 解答这个问题之前, 我们再定义⼀个名字: 影⼦状态 , ⽤变量 X 表⽰。 所谓影⼦状态, 就是和当前状态具有相同的前缀。 ⽐如下⾯这种情况:

在这里插入图片描述

当前状态 j = 4 , 其影⼦状态为 X = 2 , 它们都有相同的前缀 "AB"。 因为状态 X 和状态 j 存在相同的前缀, 所以当状态 j 准备进⾏状态重启的时候(遇到的字符 c 和 pat[j] 不匹配) , 可以通过 X 的状态转移图来获得最近的重启位置

⽐如说刚才的情况, 如果状态 j 遇到⼀个字符 "A", 应该转移到哪⾥呢?⾸先只有遇到 "C" 才能推进状态, 遇到 "A" 显然只能进⾏状态重启。 状态j 会把这个字符委托给状态 X 处理, 也就是 dp[j]['A'] = dp[X]['A'] :

在这里插入图片描述

为什么这样可以呢? 因为既然 j 这边已经确定字符 "A" ⽆法推进状态,只能回退, ⽽且 KMP 就是要尽可能少的回退, 以免多余的计算。 那么 j就可以去问问和⾃⼰具有相同前缀的 X , 如果 X 遇⻅ "A" 可以进⾏「状态推进」 , 那就转移过去, 因为这样回退最少。

当然, 如果遇到的字符是 "B", 状态 X 也不能进⾏「状态推进」 , 只能回退, j 只要跟着 X 指引的⽅向回退就⾏了:

在这里插入图片描述

你也许会问, 这个 X 怎么知道遇到字符 "B" 要回退到状态 0 呢? 因为 X永远跟在 j 的⾝后, 状态 X 如何转移, 在之前就已经算出来了动态规划算法不就是利⽤过去的结果解决现在的问题吗?

结合下面的过程理解影子状态的更新:
在这里插入图片描述

这样, 我们就细化⼀下刚才的框架代码:

int X # 影⼦状态
for 0 <= j < M:
	for 0 <= c < 256:
		if c == pat[j]:
			# 状态推进
			dp[j][c] = j + 1
		else:
			# 状态重启
			# 委托 X 计算重启位置
	dp[j][c] = dp[X][c]

五、 代码实现

如果之前的内容你都能理解, 恭喜你, 现在就剩下⼀个问题: 影⼦状态 X是如何得到的呢? 下⾯先直接看完整代码吧:

public class KMP {
	private int[][] dp;
	private String pat;
	
	public KMP(String pat) {
		this.pat = pat;
		int M = pat.length();
		
		// dp[状态][字符] = 下个状态
		dp = new int[M][256];
		
		// base case
		dp[0][pat.charAt(0)] = 1;
		
		// 影⼦状态 X 初始为 0
		int X = 0;
		
		// 当前状态 j 从 1 开始
		for (int j = 1; j < M; j++) 
		{
			for (int c = 0; c < 256; c++) 
			{
				if (pat.charAt(j) == c)
					dp[j][c] = j + 1;
				else
					dp[j][c] = dp[X][c];
			} 
			
			// 更新影⼦状态
			X = dp[X][pat.charAt(j)];
		}
	} 
	public int search(String txt) {...}
}

代码解释:

先解释⼀下这⼀⾏代码:

// base case
dp[0][pat.charAt(0)] = 1;

这⾏代码是 base case只有遇到 pat[0] 这个字符才能使状态从 0 转移到 1,遇到其它字符的话还是停留在状态 0(Java 默认初始化数组全为 0) 。

影⼦状态 X 是先初始化为 0, 然后随着 j 的前进⽽不断更新的。 下⾯看看到底应该如何更新影⼦状态 X

int X = 0;
for (int j = 1; j < M; j++) {
	...
	// 更新影⼦状态
	// 当前是状态 X, 遇到字符 pat[j],
	// pat 应该转移到哪个状态?
	X = dp[X][pat.charAt(j)];
}

更新 X 其实和 search 函数中更新状态 j 的过程是⾮常相似的:

int j = 0;
for (int i = 0; i < N; i++) {
	// 当前是状态 j, 遇到字符 txt[i],
	// pat 应该转移到哪个状态?
	j = dp[j][txt.charAt(i)];
	...
}

其中的原理⾮常微妙, 注意代码中 for 循环的变量初始值, 可以这样理解:
后者是在 txt 中匹配 pat , 前者是在 pat 中匹配 pat[1..end]状态X 总是落后状态 j ⼀个状态, 与 j 具有最⻓的相同前缀。 所以我把 X⽐喻为影⼦状态, 似乎也有⼀点贴切。另外, 构建 dp 数组是根据 base case dp[0][..] 向后推演。 这就是我认为KMP 算法就是⼀种动态规划算法的原因。

最后看KMP算法的完整代码:

public class KMP {
    private int[][] dp;
    private String pat;
​
    public KMP(String pat) {
        this.pat = pat;
        int M = pat.length();
        
        // dp[状态][字符] = 下个状态
        dp = new int[M][256];
        
        // base case
        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];
            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();
        
        // pat 的初始态为 0
        int j = 0;
        for (int i = 0; i < N; i++) {
        
            // 计算 pat 的下一个状态
            j = dp[j][txt.charAt(i)];
            
            // 到达终止态,返回结果
            if (j == M) return i - M + 1;
        }
        
        // 没到达终止态,匹配失败
        return -1;
    }
}

C++代码

//封装一个KMP算法用来快速查找字符串匹配
class KMP
{
  public:
    KMP(const std::string& pat)
      :_pat(pat)
    {
      int M = _pat.size();

      //dp[状态][字符] = 下一个状态;把dp初始化为全0
      dp = std::vector<std::vector<int>>(M,std::vector<int>(256,0));

      //base case :一开始dp中存的是0,那么规定最开始为0状态,遇到第一个字符为pat转换为1状态
      dp[0][_pat[0]] = 1;

      //博客中说的影子状态,初始化为0状态
      int X = 0;

      //开始循环构造状态转换图即dp
      for(int j = 1;j < M;j++)
      {
        for(int c = 0;c < 256;c++)
        {
          dp[j][c] = dp[X][c];
        }
        dp[j][_pat[j]] = j + 1;

        //更新影子状态
        X = dp[X][_pat[j]];
      }
    }

    int Search(const std::string& txt)
    {
      int M = _pat.size();
      int N = txt.size();

      //pat的初始状态为0状态
      int j = 0;

      //循环
      for(int i = 0;i < N;i++)
      {
        j = dp[j][txt[i]];

        //如果经过状态转换图dp可以到达终态M,就说明在txt中成功找到匹配的字符串,直接返回其在txt中的下标索引
        if(j == M)
        {
          return i - M + 1;
        }
      }

      //代码走到这里代表遍历完txt还没有找到匹配的return出去,就直接return -1;
      return -1;
    }


  private:

    //dp存放状态转换图;dp[1]['A'] = 2;代表 状态1 如果遇到字符'A',pat 就转换为2状态
    std::vector<std::vector<int>> dp;

    //用户输入pat待匹配的字符串
    std::string _pat;
};

六、 最后总结

传统的 KMP 算法是使⽤⼀个⼀维数组 next 记录前缀信息, ⽽本⽂是使⽤⼀个⼆维数组 dp 以状态转移的⾓度解决字符匹配问题, 但是空间复杂度仍然是 $O(256M) = O(M)$。

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

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

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

明确了其含义, 就可以很容易写出 search 函数的代码。

对于如何构建这个 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]] )

0

评论区