数据结构与算法(十六)

KMP算法

应用场景-字符串匹配问题

str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好"
str2 = "尚硅谷你尚硅你"

求:str2 在 str1 中是否存在,如果存在,返回第一次出现的位置,如果没有则返回 -1

暴力匹配

假设 str1 匹配到 i 位置,子串 str2 匹配到 j 位置,则:

  1. 如果当前字符匹配成功(str1[i] == str2[j]

    i++j++ 继续匹配下一个字符

  2. 如果失败(str1[i] != str2[j])则:

    i = i-(j-1)
    j = 0
    

    相当于每次匹配失败时, i 回溯,j 被重置为 0

暴力方法解决会有 大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断匹配,浪费了大量的时间。

代码实现

public class ViolenceMatch {
    public static void main(String[] args) {
        String s1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
        String s2 = "尚硅谷你尚硅你";
        int index = violenceMatch(s1,s2);
        System.out.println("index:" + index);
    }
    //str1要查找匹配的源字符串,str2要匹配的字符串
    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;//用于遍历s1
        int j = 0;//用于遍历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;
        }
        return -1;
    }
}

KMP匹配

KMP 是一个解决 模式串在文本串中是否出现过,如果出现过,则最早出现的位置的经典算法。

Knuth-Morris-Pratt 字符串查找算法,简称 KMP 算法:常用与在一个文本字符串 s 内查找一个模式串 P 的出现位置

该算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表,故取这 3 人的姓氏命名此算法.

KMP 方法利用 之前判断过的信息,通过一个 next 数组,保存模式串中前后最长公共子序列的长度,每次回溯时,通过 next 数组找到前面匹配过的位置,省去了大量的计算时间。

KMP 思路分析

Str1 = "BBC ABCDAB ABCDABCDABDE"
Str2 = "ABCDABD"
  1. 都用第 1 个字符进行比较,不符合,关键词(文本串)向后移动一位
    数据结构与算法(十六)

  2. 重复第一步,还是不符合,再后移动
    数据结构与算法(十六)

  3. 一直重复,直到 str1 有一个字符与 str2 的第一个字符匹配为止
    数据结构与算法(十六)

  4. 接着比较字符串和搜索词的下一个字符,还是符合
    数据结构与算法(十六)

  5. 遇到 st1 有一个字符与 str2 对应的字符不符合时
    数据结构与算法(十六)

  6. 这时候:想到的是继续遍历 st1 的下一个字符(也就是暴力匹配)
    数据结构与算法(十六)

这时,就出现一个问题:
数据结构与算法(十六)

此时回溯时,A 还会去和 BCD 进行比较,而在上一步 ABCDAB 与 ABCDABD,前 6 个都相等,其中 BCD 搜索词的第一个字符 A 不相等,那么这个时候还要用 A 去匹配 BCD,这肯定会匹配失败。

KMP 算法的想法是:设法利用这个已知信息,不要把「搜索位置」移回已经比较过的位置,继续把它向后移,这样就提高了效率。

那么新的问题就来了:你如何知道 A 与 BCD 不相同,并且只有 BCD 不用比较呢?这个就是 KMP 的核心原理了。

  1. KMP 利用 部分匹配表,来省略掉刚刚重复的步骤。
    数据结构与算法(十六)

上表是这样看的:

  1. ABCD 匹配值 0
  2. ABCDA 匹配值 1
  3. ABCDAB 匹配值 2

至于如何产生的这个部分匹配表,下面专门讲解,这里你要知道的是,KMP 利用这个 部分匹配表 可以省略掉重复的步骤

  1. 已知空格与 D 不匹配时,前面 6 个字符 ABCDAB 是匹配的。
    数据结构与算法(十六)

查表可知:部分匹配值是 2,因此按照下面的公司计算出后移的位数:移动位数 = 已匹配的字符数 - 对应的部分匹配值

  1. 逐位比较,直到搜索词(文本串)的最后一位,发现完全匹配,搜索完成。

部分匹配表是如何产生的?

看上上述步骤,你现在的疑惑是:这个部分匹配表是如何产生的?下面就来介绍

需要先知道 **前缀 ** 和 后缀 是什么
数据结构与算法(十六)

  • 前缀:仔细看,它的前缀就是每个字符串的组合,逐渐变长,但是不包括最后一个字符

    如果 bread 是字符串 bread 的前缀,这个不是完全匹配了吗?

  • 后缀:同理,不包含第一个

部分匹配值 就是 前缀后缀最长的共有元素的长度,下面以 ABCDABD 来解说:

字符串 前缀 后缀 共有元素 共有元素长度
A - - - 0
AB A B - 0
ABC A、AB BC、C - 0
ABCD A、AB、ABC BCD、CD、D - 0
ABCDA A、AB、ABC、ABCD BCDA、CDA、DA、A A 1
ABCDAB A、AB、ABC、ABCD、ABCDA BCDAB、CDAB、DAB、AB、B AB 2
ABCDABD A、AB、ABC、ABCD、ABCDA、ABCDAB BCDABD、CDABD、DABD、ABD、BD、D - 0

部分匹配 的实质是:有时候,字符串头部和尾部会有重复。

比如:ABCDAB 中有两个 AB ,那么它的 部分匹配值 就是 2 (AB 的长度),搜索词(文本串)移动的时候,第一个移动 4 位(字符串长度 - 部分匹配值),就可以来到第二个 AB 的位置,从而跳过了已经匹配过的 BCD。
数据结构与算法(十六)

如果还是想刨根问底,可以去参考下这篇文章:写得很详细](https://www.cnblogs.com/zzuuoo666/p/9028287.html),应该需要一些数学知识才能看懂。

KMP 代码实现

/**
     * KMP搜索算法
     * @param str1 源字符串
     * @param str2 匹配字符串
     * @param next 部分匹配表
     * @return 找到就返回首字母下标,没有找到返回-1
     */
    public static int KMPSearch(String str1,String str2,int[] next){
        for(int i = 0,j = 0; i < str1.length();i++){
            //如果不相等就回退
            while(j > 0 && str1.charAt(i) != str2.charAt(j)){
                j = next[j-1];
            }
            if(str1.charAt(i) == str2.charAt(j)){
                j++;
            }

            if(j == str2.length()){
                //全部匹配结束
                return i - j + 1;
            }
        }
        return -1;//没有匹配到
    }
    //求KMP算法部分匹配表
    public static int[] kmpNext(String str1){
        int[] next = new int[str1.length()];
        next[0] = 0;//第一个元素的匹配值一定是0
        for(int i = 1,j = 0; i < str1.length();i++){
            while(j > 0 && str1.charAt(i) != str1.charAt(j)){
                j = next[j-1];
            }
            if(str1.charAt(i) == str1.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }

贪心算法

应用场景-集合覆盖问题

贪心算法可以解决很多场景的问题,这里以集合覆盖问题为例。

假设存在下面需要付费的广播台,以及广播台信号可以覆盖的地区。如何选择最少的广播台,让所有的地区都可以接收到信号?

广播台 覆盖地区
K1 "北京", "上海", "天津"
K2 "广州", "北京", "深圳"
K3 "成都", "上海", "杭州"
K4 "上海", "天津"
K5 "杭州", "大连"

例如:k4 中有上海、天津,那么我们选择 k1,里面包含了他们,还多了一个地区。

贪心算法介绍

**贪婪算法(贪心算法) **是指在对问题进行求解时,在 每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法

贪婪算法所得到的 结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果

思路分析

如何找出覆盖所有地区的广播台的集合呢,最容易想到的是使用穷举法实现,列出每个可能的广播台的集合,这被称为 幂集。假设总的有 n 个广播台,则广播台的组合总共有 2ⁿ -1 个,假设每秒可以计算 10 个子集, 如图:

广播台数量n 子集总数2ⁿ 需要的时间
5 32 3.2秒
10 1024 102.4秒
32 4294967296 13.6年
100 1.26*100³º 4x10²³年

由此可见:在进行组合的场景下,使用组合效率是很低的。

那么贪心算法的思路如下:

广播台 覆盖地区
K1 "北京", "上海", "天津"
K2 "广州", "北京", "深圳"
K3 "成都", "上海", "杭州"
K4 "上海", "天津"
K5 "杭州", "大连"

目前并没有算法可以快速计算得到准备的值, 使用贪婪算法,则可以得到非常接近的解,并且效率高。选择策略上,因为需要覆盖全部地区的最小集合,思路如下:

  1. 将所有需要覆盖的地区找出来(allAreas)也就是所有电台中的覆盖地区去重后的列表

  2. 遍历所有的广播电台,找到一个 覆盖了最多未覆盖的地区 的电台,此电台可能包含一些已覆盖的地区,但是没有关系。

    比如:k1 中有三个地区,在上面找出来的列表中去判定是否覆盖其中的地区,找到则 k1 为 覆盖了最多未覆盖的地区 的电台。

  3. 将这个电台加入到一个集合中(如 ArrayList),并想办法把该电台覆盖的地区在下次比较时去掉。

    比如:前面 k1 为 覆盖了最多未覆盖的地区,把 k1 加到该集合中,并从把 k1 已经覆盖过的地区从 allAreas 中移除

  4. 重复第 2 步,直到覆盖了全部的地区

图解

给定的广播电台如下

广播台 覆盖地区
K1 "北京", "上海", "天津"
K2 "广州", "北京", "深圳"
K3 "成都", "上海", "杭州"
K4 "上海", "天津"
K5 "杭州", "大连"
  1. 找出所有需要覆盖的地区

    allAreas = {"北京", "上海", "天津", "广州", "深圳", "成都", "杭州", "大连"}
    
  2. 遍历广播电台列表:找出一个覆盖了最多地区的电台,重点:如何确定覆盖了最多的电台?

    可以这样做:遍历广播台,计算每个电台中覆盖的地区在未覆盖地区列表中,覆盖了几个?

    广播台 覆盖地区 覆盖数量(未覆盖地区的数量)
    K1 "北京", "上海", "天津" 3
    K2 "广州", "北京", "深圳" 3
    K3 "成都", "上海", "杭州" 3
    K4 "上海", "天津" 2
    K5 "杭州", "大连" 2

    上图覆盖数量计算,例如:k1 覆盖地区有三个,这三个地区现在都在 未覆盖地区(allAreas),所以:k1 的覆盖数量则是 3

  3. 找到覆盖数量最大的电台(每一步的选择都选择最优)

    上第 2 步骤中,计算出的覆盖数量,k1 为最大的(k2 也是 3,但是不大于 k1 的覆盖数量),计为 maxKey,将它添加到 选择列表中,表示该电台已被选择,同时将 k1 中覆盖地区,从 allAreas 列表中去掉,那么现在的情况就如下:

    // 已选电台
    selects =  {"k1"}
    // 未覆盖地区
    allAreas = {广州", "深圳", "成都", "杭州", "大连"}
    
  4. 重新计算未被选择的电台的覆盖数量

    // 已选择电台
    selects =  {"k1"}
    // 所有暂时还未覆盖的地区列表
    allAreas = {广州", "深圳", "成都", "杭州", "大连"}
    
    广播台 覆盖地区 覆盖数量(未覆盖地区的数量)
    K1 "北京", "上海", "天津" 0
    K2 "广州", "北京", "深圳" 2
    K3 "成都", "上海", "杭州" 2
    K4 "上海", "天津" 0
    K5 "杭州", "大连" 2

    注意:因为 k1,已经被选择过,可以不重新对它计数,也可以重新计数,对性能影响不太大。

    上图覆盖数量计算,例如:

    • k1 覆盖地区有三个,这三个地区现在在 未覆盖地区(allAreas)中一个都没有,所以:k1 的覆盖数量则是 0
    • k2 覆盖的确有三个,这三个地区现在在 未覆盖地区(allAreas)中有 2 个:广州、深圳,而北京已经被覆盖掉了(k1),所以:k2 的覆盖数量则是 2
  5. 找到覆盖数量最大的电台,重复上面的过程,直到allAreas为空为止。

代码实现

//贪心算法解决集合覆盖问题
public class GreedyAlgorithm {
    public static void main(String[] args) {
        //使用HashMap定义所有的广播
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        HashSet<String> hashSet1 = new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");

        HashSet<String> hashSet2 = new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");

        HashSet<String> hashSet3 = new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");

        HashSet<String> hashSet4 = new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");

        HashSet<String> hashSet5 = new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");

        broadcasts.put("K1",hashSet1);
        broadcasts.put("K2",hashSet2);
        broadcasts.put("K3",hashSet3);
        broadcasts.put("K4",hashSet4);
        broadcasts.put("K5",hashSet5);

        //保存所有地区
        HashSet<String> allAreas = new HashSet<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");
        //用于保存选择的电台
        ArrayList<String> selects = new ArrayList<>();

        HashSet<String> tempSet = new HashSet<>();//临时变量
        String keyMax = null;//用于保存包含最多未包含的地区的key
        while(allAreas.size() > 0){
            keyMax = null;//重置keyMax
            for(String key : broadcasts.keySet()){
                tempSet.clear();//清空已经包含的元素
                HashSet<String> areas = broadcasts.get(key);//获取当前广播可以播放的所有地区
                tempSet.addAll(areas);
                tempSet.retainAll(allAreas);//取得可以覆盖多少未覆盖的地区,取交集
                if(tempSet.size() > 0 && (keyMax == null || tempSet.size() > broadcasts.get(keyMax).size())){
                    keyMax = key;
                }
            }

            if(keyMax != null){
                selects.add(keyMax);//将电台加入选择集合中
                allAreas.removeAll(broadcasts.get(keyMax));//移出所有包含的元素
            }

        }

        System.out.println(selects);

    }
}

贪婪算法注意事项

贪婪算法所得到的结果 不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果

比如上题的算法选出的是 K1, K2, K3, K5,符合覆盖了全部的地区,但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区,如果 K2 的使用成本低于 K1 ,那么我们上题的 K1, K2, K3, K5 虽然是满足条件,但是并不是最优的.

但是笔者觉得上述举例并不是问题:如果加上成本:那么只要在 maxKey 覆盖数量相等的情况下,判定采用成本更低的 key,则可解决这个问题。

上一篇:3.Python基础-数据类型


下一篇:不同环境相同配置项的内容如何diff差异?