算法之KMP

KMP算法:squirrel:

kmp算法是为了解决传统字符串匹配问题而诞生的

有以下两个字符串A和B,长度分别为 N 和 M,判断B是否是A的子串,以及开始匹配的位置,不匹配就返回-1
A:”ababababca”
B:”abababca”

传统的方法就是主串和目标串对位比较,不对则主串重新从下一位开始,时间复杂度接近 O( N × M )

而kmp算法精妙之处在于通过找寻目标串 B 每一位的信息,利用这个信息,使得在字符不匹配的情况下,不需要整体重新来过,只需要移动一定的位置,然后继续匹配即可。

而这个信息就是——前缀与后缀相等的最大长度:boom::boom::boom:

下面介绍一下kmp到底如何加速字符串匹配的!

  • 首先生成字符串B的 next 数组,而这个数组的含义是: next[i]表示 next[0....i-1]前缀与后缀相等的最大长度,举个例子:”abababca”这个字符串中 字符 ‘c’ 的前缀和后缀相同的有 前缀”abab” 和 后缀 “abab”是最大的,故 字符”c” 的next数组位置就是 4
    下图展示了”abababca”的next数组:

算法之KMP

  • 生成了这个next数组之后,我们就可以加速主串和目标串的匹配过程了
    对于主串”ababababca”,当目标串”abababca”匹配到下标为 j 时,发现 'a' != 'c',此时主串并没有重新从i = 1开始匹配,而是让目标串的 j 开始跳,跳到next[j]的下标,即 j = 4,即从 j = 4开始与i继续匹配!如下图所示

算法之KMP

那这样做的原理是什么呢 :question:

如下图

首先当主串和目标串匹配到A 和 B 字符的时候发生不匹配,我们知道 1 区域等于3 区域,而 3 区域等于2区域,故1区域一定等于2区域,因为next的数组的定义就是这样,前缀和后缀相等的最大长度,所以这次不需要主串重新回到 i + 1 的 位置,只需要目标串退回到2区域最后位置 + 1 ,直接从目标串的 C字符开始和 A 字符匹配即可:exclamation: :exclamation: :exclamation:

理解了之后,直接上代码!

public class Main(){
    public static void main(String[] args){

    }
    public int kmp(String s1, String s2){
        if(s1 == null || s2 == null || s2.length() > s1.length() || s2.length() == 0){
            return -1;
        }
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        int len1 = arr1.length;
        int len2 = arr2.length;
        int[] next = getNext(arr2);
        int i = 0;
        int j = 0;
        while(i < len1 && j < len2){
            if(arr1[i] == arr2[j]){
                i++;
                j++;
            }else if(next[j] == -1){
                i++;
            }else{ //加速的过程体现在这,如果两个字符不相等,j 是跳到 最大前缀长度的下一个位置
                j = next[j];
            }
        }
        return j == len2 ? i - j : -1; 
    }

    public int[] getNext(char[] arr){
        if(arr.length == 1){
            return new int[]{-1};
        }
        int len = arr.length;
        int[] next = new int[len];
        next[0] = -1;
        next[1] =  0;
        int pos = 0;
        int cur = 2;
        while(cur < len){
            if(arr[pos] == arr[cur - 1]){
                next[cur] = pos + 1;
                cur++;
                pos++;
            }else if(next[pos] > 0){
                pos = next[pos];
            }else{
                next[cur] = 0;
                cur++;
            }
        }
        return next;
    }
}

kmp的应用可以用在判断一棵树是否是另一颗树的子树!!!时间复杂度控制在O(M + N) M和N为两个树的结点数。感觉树的拓扑结构复杂的情况下用kmp不错,用递归的话接近O(M × N)

public boolean isSubTree(TreeNode A, TreeNode B) {
        if(A==null||B==null){
            return false;
        }
        return kmp(preString(A),preString(B)) != -1; //kmp一判断,完事!
    }
    public String preString(TreeNode root1) {
        //先找到两棵树的先序序列
        if (root1 == null) {
            return "!_";
        }
        String s = root1.val + "_";
        s += preString(root1.left);
        s += preString(root1.right);
        return s;
    }

算法之KMP

此题的递归解法::eyes:
public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null && t != null){
            return false;
        }
        if(s == null && t == null){
            return true;
        }
        //无非就是,两个树相同,t是s的左子树,t是s的右子树!这三种情况
        return isSameTree(s,t) || isSubtree(s.left,t) || isSubtree(s.right,t);

    }

    public boolean isSameTree(TreeNode s, TreeNode t){
        if(s == null && t == null){
            //两树都一起到达底部
            return true;
        }
        if(s == null || t == null){
            //一个树有值,另一个树为空,则一定不为子树
            return false;
        }
        if(s.val != t.val){
            //不相等则更不用说
            return false;
        }
        return isSameTree(s.left,t.left) && isSameTree(s.right,t.right);
    }

算法之KMP

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!