美文网首页
字符串-KMP算法

字符串-KMP算法

作者: freemanIT | 来源:发表于2022-04-08 18:10 被阅读0次

字符串-KMP算法

若干个字符组成字符串

string字符串

字符串前缀prefix, 真前缀proper prefix, 后缀suffix, 真后缀proper suffix

前缀后缀真前缀真后缀

串匹配算法

查找一个模式串(pattern)在文本串(text)中的位置

经典的串匹配算法

  • 蛮力 Brute Force
  • KMP
  • Boyer-Moore
  • Karp-Rabin
  • Sunday

蛮力算法

以字符为单位, 从左到右移动模式串, 直到匹配成功

蛮力算法逐个比较

蛮力1

pi 的取值范围[0, plen)

ti 的取值范围[0, tlen)

蛮力1执行过程1

pi = 0

ti -= pi - 1

当pi == plen 时, 成功匹配

蛮力1执行过程2
    public static int index(String text, String pattern) {
        // 检测合法性
        if (text == null || pattern == null) return -1;
        char [] textChars = text.toCharArray();
        int tlen = textChars.length;
        char [] patternChars = pattern.toCharArray();
        int plen = patternChars.length;
        if (tlen == 0 || plen == 0 || tlen < plen) return -1;
        
        int pi = 0, ti = 0;
        while (pi < plen && ti < tlen) {
            if (textChars[ti] == patternChars[pi]) {
                ti++;
                pi++;
            } else {
                ti = ti - pi + 1;
                pi = 0;
            }
        }
        return pi == plen ? ti - pi : -1;
    }

优化

在后几位匹配成功后, 长度超出字符串的范围, 提前退出

ti 的退出条件为

  • ti - pi <= tlen - plen
  • ti - pi, 是指每一轮比较中text 的首个比较字符的位置
蛮力1优化
    /**
     * 改进
     * @param text
     * @param pattern
     * @return
     */
    public static int index2(String text, String pattern) {
        // 检测合法性
        if (text == null || pattern == null) return -1;
        char [] textChars = text.toCharArray();
        int tlen = textChars.length;
        char [] patternChars = pattern.toCharArray();
        int plen = patternChars.length;
        if (tlen == 0 || plen == 0 || tlen < plen) return -1;
        
        int pi = 0, ti = 0;
        while (pi < plen && ti - pi < tlen - plen) {
            if (textChars[ti] == patternChars[pi]) {
                ti++;
                pi++;
            } else {
                ti = ti - pi + 1;
                pi = 0;
            }
        }
        return pi == plen ? ti - pi : -1;
    }

蛮力2

pi 的取值范围[0, plen)

ti 的取值范围[0, tlen - plen)

逐个比较

pi = 0

ti++

pi == plen 时, 成功匹配

蛮力2比较失败
    public static int index(String text, String pattern) {
        // 检测合法性
        if (text == null || pattern == null) return -1;
        char [] textChars = text.toCharArray();
        int tlen = textChars.length;
        char [] patternChars = pattern.toCharArray();
        int plen = patternChars.length;
        if (tlen == 0 || plen == 0 || tlen < plen) return -1;
        
        int tiMax = tlen = plen;
        for (int ti = 0; ti < tiMax; ti++) {
            int pi = 0;
            for (; pi < plen; pi++) {
                if (textChars[ti + pi] != patternChars[pi]) break;
            }
            if (pi == plen) return ti;
        }
        return -1;
    }

蛮力性能分析

n 是文本串长度, m 是模式串长度

最多n - m + 1 轮比较

最好的情况下

  • 只需一轮比较, 匹配成功, 比较m 次, 时间复杂度O(m)

最坏情况下

  • 执行n - m + 1 轮比价
  • 每轮都比较至模式串的末字符后失败, m - 1 次成功, 1 次失败
  • 时间复杂度为O(m*(n-m+1)), 由于一般m 远小于n, 所以O(mn)
性能分析

KMP

预先根据模式串内容生成一张next 表

next表

比较字符不等时, 在next 表中找到之前模式串的最大公共子串长度

next的使用

原理:

  • 当d, e 失配, 如果pattern 能够一次性向右移动一大段距离, 比较d 和c 字符
    • A 和B 相等
  • 所以KMP 必须在失配字符e 左边的子串中找出符合条件的AB, 从而得知向右移动的距离
  • 向右移动的距离: e 左边子串长度 - A 的长度 == e 的索引 - c 的索引, 且c 的索引 == next[e的索引], 所以向右移动距离: e 的索引 - next[e的索引]

总结

  • 如果在pi 位置失配, 向右移动的距离是pi - next[pi], 所以next[pi] 越小, 移动距离越大
  • next[pi] 是pi 左边子串真前缀后缀的最大公共子串长度
核心原理 最大长度

向右移动一位得到next 表

next表
    public static int indexOf(String text, String pattern) {
        // 检测合法性
        if (text == null || pattern == null) return -1;
        char [] textChars = text.toCharArray();
        int tlen = textChars.length;
        char [] patternChars = pattern.toCharArray();
        int plen = patternChars.length;
        if (tlen == 0 || plen == 0 || tlen < plen) return -1;
        // 得到next 表
        int[] next = next(pattern);
        
        int pi = 0, ti = 0;
        while (pi < plen && ti < tlen) {
            // next 第一个位置置为-1, 当pi == -1, 则pi = 0, ti++, 相当于模式串向后移动一位
            if (pi < 0 || textChars[ti] == patternChars[pi]) {
                ti++;
                pi++;
            } else {
                pi = next[pi];
            }
        }
        
        return pi == plen ? ti - pi : -1;
    }

为什么是最大公共子串长度

  • 将3 赋值pi, 向右移动1 个字符单位, 最后成功匹配
  • 将1 赋值pi, 向右移动3 个字符单位, 错过错过匹配机会

公共子串长度越小, 向右移动距离越大, 越不安全

公共子串长度越大, 向右移动距离越小, 越安全

如果相同得到next表 字符相同直接跳到第一个位置

构造思路

next[i] == n

  1. 如果pattern.charAt(i) == pattern.charAt(n)
    1. 则next[i + 1] == n + 1
  2. 如果pattern.charAt(i) != pattern.charAt(n)
    1. 已知next[n] == k
    2. 如果pattern.charAt(i) == pattern.charAt(k)
      1. 则next[i + 1] == k + 1
    3. 如果pattern.charAt(i) != pattern.charAt(k)
      1. 将k 带入n, 重复执行这个比较2
构造next思路
    private static int[] next2(String pattern) {
        char[] chars = pattern.toCharArray();
        int[] next = new int[chars.length];
        
        next[0] = -1;
        int i = 0;
        int n = -1;
        int iMax = chars.length - 1;
        while (i < iMax) {
            if (n < 0 || chars[i] == chars[n]) {
                next[++i] = ++n;
            } else {
                n = next[n];
            }
        }
        return next;
    }

不足, 如果遇到相同字符的内容, 则不必要比较

遇到相同字符

优化思路

next[i] == n, next[n] == k

如果pattern[i] != d, 就让模式串滑动到next[i], n 的位置, 跟d 进行比较

如果pattern[n] != d, 就让模式串滑动到next[n], k 的位置, 跟d 进行比较

如果pattern[i] == pattern[n], 那么当i 位置失配, 模式串最终必然滑动到k 位置跟d 进行比较

所以, next[i] 直接存储next[n] 即可

优化思路 next优化后
    private static int[] next(String pattern) {
        char[] chars = pattern.toCharArray();
        int[] next = new int[chars.length];
        
        next[0] = -1;
        int i = 0;
        int n = -1;
        int iMax = chars.length - 1;
        while (i < iMax) {
            if (n < 0 || chars[i] == chars[n]) {
                ++i;
                ++n;
                if (chars[i] == chars[n]) {
                    next[i] = next[n];
                } else {
                    next[i] = n;
                }
            } else {
                n = next[n];
            }
        }
        return next;
    }

性能分析

KMP 主要逻辑

最好时间复杂度O(m)

最坏时间复杂度O(n), 不超过O(2n)

next 表构造过程跟kmp 主体逻辑类似, 时间复杂度O(m)

所以得到整体

最好时间复杂度O(m)

最坏时间复杂度O(n + m)

空间复杂度O(m)

BM

Boyer-Moore, 简称BM

  • 最坏时间复杂度O(n/m), 最坏为O(n + m)
  • 从模式串的尾部开始匹配

2 条计算规则计算出最大值

  • 坏字符规则(Bad Character, BC)
  • 好后缀规则(Good Suffix, GS)

坏字符规则

当pattern 中的字符E 和text 中的S 失配时, 称S 为坏字符

  • 如果pattern 的未匹配子串中不存在坏字符, 直接将pattern移动到坏字符的下一位
  • 否则, 让pattern 的未匹配子串中最靠右的坏字符与text 中的坏字符对齐
bm算法 好后缀

好后缀规则

MPLE 是一个成功匹配的后缀, E, LE, PLE, MPLE 都是好后缀

  • 如果pattern 中找不到与好后缀对齐的子串, 直接将pattern 移动到好后缀的下一位
  • 否则, 从pattern 中找出子串与text 中的好后缀对齐
好后缀

BM 分析

最好情况, 时间复杂度O(n/m)

最好情况

最坏情况, 时间复杂度O(n + m), 其中O(m) 为构造表的时间

最坏情况

Sunday

思路和BM 类似

  • 从前向后匹配

  • 当失配时, 关注的是text 中参与匹配的正常的下一位字符A

    如果A 没有在pattern 中出现, 则直接跳过, 即 移动位数 = pattern + 1

    否则, 让pattern 中最靠右的A 与text 中的A 对齐

Sunday

相关文章

  • KMP算法文章合集

    字符串的查找:朴素查找算法和KMP算法 暴力匹配算法与KMP算法(串的匹配) 字符串查找算法BF和KMP 字符串匹...

  • 算法(2)KMP算法

    1.0 问题描述 实现KMP算法查找字符串。 2.0 问题分析 “KMP算法”是对字符串查找“简单算法”的优化。 ...

  • KMP算法——寻找子串位置

    KMP算法——寻找子串位置 1、KMP算法简介: KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J....

  • KMP算法(字符串匹配问题)

    一、是什么? 注意,是KMP算法,不是MMP哈,我没有骂人。KMP算法是用来做字符串匹配的,除了KMP算法分,还有...

  • 字符串匹配与KMP算法

    1.朴素字符串匹配算法 2.KMP算法 求前缀函数 实现KMP算法 3.测试代码

  • KMP算法理解

    文章大纲:1.KMP算法概念2.KMP算法中最核心的next[] 数组是如何生成的3.使用KMP算法 匹配字符串 ...

  • leetcode字符串匹配算法之KMP算法

    本篇介绍一种高效的字符串匹配算法——KMP算法。 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J....

  • JavaScript 二分查找 & KMP 算法

    KMP 查找 Knuth-Morris-Pratt字符串查找算法(简称为KMP算法)可在一个主文本字符串 str1...

  • KMP算法:求next数组,一听就会

    KMP算法是啥? KMP算法就是一种字符串匹配算法,简单说就是从一个长字符串中搜索一个短字符串(也叫模式串)。这个...

  • KMP算法

    KMP算法是解决字符串匹配问题的有高效算法 代码:

网友评论

      本文标题:字符串-KMP算法

      本文链接:https://www.haomeiwen.com/subject/kfvtsrtx.html