KMP算法
发布日期:2021-05-10 06:29:35 浏览次数:21 分类:技术文章

本文共 3856 字,大约阅读时间需要 12 分钟。

题目:

  • 如我有两个字符串
    String str1 = "BBC ABCDAB ABCDABCDABDE"
    String str2 = "ABCDABD"
    (空格别忽略了)需要求str2在str1中第一次出现的位置,现在用人眼看来实在下标19处

暴力算法:

过程:

  1. 初始化,首先将这两个字符串转成char数组

    并创建连个索引:i、j分别记录str1、str2匹配位置。
    在这里插入图片描述

  2. 开始匹配,第一遍

    在这里插入图片描述
    没匹配成功:i往后移一位,j回到str2头

  3. 第二遍

    在这里插入图片描述
    省略n遍。。。

  4. 第十一遍

    在这里插入图片描述这时候又得回头,索引回溯:
    i = i - j + 1;
    j = 0;

  5. 第十二遍

    在这里插入图片描述
    复杂度想想都恐怖
    暴力法实现:

public static int violenceMatch(String str1, String str2) {
char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int s1len = s1.length; int s2len = s2.length; int i = 0, j = 0; while (i

KMP算法:

先不讲next数组的形成过程,首先了解以下匹配过程:

在这里插入图片描述

在这里插入图片描述
此时发现不匹配,无需将j回溯到0,而是回溯到next[j]处。
移动位数 = j - next[j]
在这里插入图片描述
接着再进行匹配

next数组

  • 我们每次进行移动只关注前面已经匹配的字符,与后面无关,所以next数组的元素就是每个匹配中的字符与前面元素组成的字符串的前缀和后缀的最长的公共元素的长度,因此其求法与动态规划的dp数组相似
  • 举例子:
    "ababc"
前n个字符组成的字符串 前缀 后缀 前缀和后缀的最长的公共元素的长度
a 0
ab a b 0
aba a,ab a,ba 1
abab a,ab,aba b,ab,bab 2
ababc a,ab,aba,abab c,bc,abc,babc 0

初步结果:next[] = {0,0,1,2,0};

最终结果需要把每个元素进行后移一位,next[0]处为-1:next[] = {-1,0,0,1,2};

说是当上面这么说,那有没有一种好求法呢?

利用动态规划知识
其实我们只需对比str2.charAt(j)是否等于 str2.charAt(next[j - 1])即可,如果相等则next[j] = next[j - 1] + 1
如果不相等,则需要递归的比较,直到相等或者next[j - 1]=0;相等则置为递归到的next[n]+1,否则置为0
话说一大堆没实质用处,接下来看图解:

  1. 初始值:
    在这里插入图片描述
  2. 比较str2.charAt(j) = B,str2.charAt(next[j - 1]) = A,发现不相等并且next[j - 1]==0,不进行递归,置0
    在这里插入图片描述
  3. 比较str2.charAt(j) = A,str2.charAt(next[j - 1]) = A,发现相等,置为next[j - 1] + 1=1
    在这里插入图片描述
  4. 比较str2.charAt(j) = B,str2.charAt(next[j - 1]) = B,发现相等,置为next[j - 1] + 1=2
    在这里插入图片描述
  5. 比较str2.charAt(j) = C,str2.charAt(next[j - 1]) = A,发现不相等,递归到str2.charAt(next[next[j-1]-1])=B不相等,本想再递归,此时发现next[next[j-1]-1]==0不再递归,置为0
    在这里插入图片描述
    如此反复求出next初始数组,再进行右移即可。
    代码实现
public static int[] kmpNext(String dest) {
//创建next数组保存部分匹配值 int [] next = new int[dest.length()]; next[0] = 0; //记录匹配到公共前后缀长度 int len = 0; int i = 1; while (i < dest.length()) {
if (dest.charAt(i) == dest.charAt(len)) {
len++; next[i] = len; i++; }else {
if (len > 0) {
len = next[len -1]; }else {
next[i] = len; i++; } } } for (int j = next.length-1; j > 0; j--) {
next[j] = next[j - 1]; } next[0] = -1; return next;}

完整代码:

package Algorithm;import java.util.Arrays;import javax.xml.soap.Text;public class KMP {
public static void main(String[] args) {
String s1 = "bbc abcdab abcdabcdabcde"; String s2 = "abcdabcd"; int violenceMatch = Match.violenceMatch(s1, s2); System.out.println(violenceMatch); int[] next = Match.kmpNext(s2); int index = Match.kmpSearch(s1, s2, next); System.out.println(Arrays.toString(next)); System.out.println(index); }}class Match {
public static int kmpSearch(String str1, String str2, int[] next) {
// 遍历 int j = 0; int i = 0; while (i < str1.length()) {
if (j == str2.length()-1 && str1.charAt(i) == str2.charAt(j) ) {
return i - j; //j = next[j];需要找多个匹配的地方 } if (str1.charAt(i) == str2.charAt(j)) {
i++; j++; }else {
j = next[j]; if (j == -1) {
i++; j++; } } } return -1; } /** * @param dest 要匹配的子字符串 * @return */ public static int[] kmpNext(String dest) {
// 创建next数组保存部分匹配值 int[] next = new int[dest.length()]; next[0] = 0; // 记录匹配到公共前后缀长度 int len = 0; int i = 1; while (i < dest.length()) {
if (dest.charAt(i) == dest.charAt(len)) {
len++; next[i] = len; i++; } else {
if (len > 0) {
len = next[len - 1]; } else {
next[i] = len; i++; } } } for (int j = next.length - 1; j > 0; j--) {
next[j] = next[j - 1]; } next[0] = -1; return next; } public static int violenceMatch(String str1, String str2) {
char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int s1len = s1.length; int s2len = s2.length; int i = 0, j = 0;// i索引指向s1 j指向s2 while (i < s1len && j < s2len) {
// 匹配不越界 if (s1[i] == s2[j]) {
i++; j++; } else {
i = i - (j - 1);// 指向下一个字符,别多想暴力算法就移动一个位置而已 j = 0; } } if (j == s2len) {
return i - j; } else {
return -1; } }}

转载地址:https://blog.csdn.net/weixin_43860530/article/details/106863428 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:OpenGL学习---环境搭建
下一篇:哈夫曼树及哈夫曼编码到底是怎么回事儿?

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2024年07月02日 16时01分36秒