写在前面

数据结构全文

字符串匹配问题（KMP算法）

暴力匹配法

public static int violenceMath(String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int s1len = s1.length;
    int s2len = s2.length;
    int i = 0;
    int j = 0;
    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;
    }
}
复制代码

KMP算法

部分匹配值，是前缀和后缀最长的共有元素的长度
根据部分匹配值进行偏移，可以确定的一点是，在当前匹配不成功的两个部分中匹配成功的部分，如果子串头尾是存在重叠位置的，那么就可以从目标串中匹配成功的部分的重叠位置开始比较，可以保证从重叠的位置开始，一定存在成功率的

例如，两个字符串str1ABCDABDDD与str2ABCDABC，其实从头开始比较，当比较到str1[5]的位置与str2[5]时发现，匹配不成功了，但是此时str2中ABCDAB的头尾AB有两个重复的字符串，此时部分匹配值是2，可以确定的第一个条件是str1的前6个与str2的前6个是相等的，第二条件是str2中ABCDAB前后缀只有前面两个和后面两个是重复的，那么可以明确，从str1ABCD任意一个开始都不会匹配成功，因为部分匹配值只有2，也就是说对应相同的字符串AB在str1的BCD任意一个位置起都找不到相同的AB，只能在D后才能找到AB，也就是移动已匹配成功的字符串长度-部分匹配值

那么如果字符串是str1ABCDDD与str2ABCDE，此时代表，共同的匹配的字符串，此时部分匹配值均为0，那么就表示str1中的ABCD从任意一个位置开始，都不能匹配成功，只能跳过这个字符串

代码及解释

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++) {
        //当不相等的时候，去调整j的大小
        //先看后文的解释
        //相当于在str1中找str2中后缀的位置，换句话说就是在目前已匹配上的部分字符串中
        //将str2的前缀移动到str1那个匹配上的部分字符串的后缀上
        //再比较`str2前缀`后面的那一个字符
        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;
}
复制代码

获取各个字符的部分匹配值

public static int[] kmpNext(String dest) {
    //创建next数组保存部分匹配值
    int[] next = new int[dest.length()];
    next[0] = 0; //如果字符串长度为1，部分匹配值就是0
    for (int i = 1, j = 0; i < dest.length(); i++) {
        //i向后找后缀，j指向前缀
        while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
            //看后文的解释
            j = next[j-1];
        }
        if (dest.charAt(i) == dest.charAt(j)) {
            //又代表部分匹配值的值，又能代表当前前缀在字符串的位置
            j ++;
        }
        next[i] = j;
    }
    return next;
}
复制代码

核心代码j = next[j-1]详解，前提需要能手算匹配值

第一步，先阐述一下next[i]=j 非0的含义，能表示部分匹配值，表示这个位置前后缀最长的长度（如next[3]=2的含义就是，到下标为3，总长为4的字符串为止，前后缀最长的长度为2，那么也就是前两个等于后两个的意思，例如str为ABAB，str[0…1]= str[1…2]）；又能代表当前位置匹配的前缀的下标+1（如next[5]=1的含义就是下标为5的字符，与str[0]相同，也就是str[5]=str[0]），指向前缀的下一个位置

第二步，解释获取各个字符的部分匹配值中，这个回溯j操作的含义，先上结论，目的是检查待检查的字符前面是否已经存在部分前缀。为了阐明这个过程，这里有两个概念小前缀和大前缀，例如strABABABC，经过前面的比较，现在已经比较到i=6的位置，next[0~5]={0,1,2,3,4}，而此时j=4，对于前面的字符串ABABAB来说，假如str[6]=A，那么next[5]=5，这是很明显的，但是此时显然str[4]!=str[5]，那么按道理来说，应该让j=0，也就是从头开始匹配，但是实际上这是错的，对于cbcc cbcc b这个字符串显然不行；那么就选择回到了假设的大前缀ABABA的小前缀AB的后面一位，也就是比较str[2]与str[5]，这样如果还不相等，那就证明只能回到j=0的位置；那么问题的关键来了，为什么可以在这个大前缀中找到小前缀，而且这个小前缀恰恰与待比较的字符的前面相等呢？

下面的例子和第三步一起看

这里举个例子，字符串cbcc cbcc b，next[0…7]={0,0,1,1,1,2,3,4}，匹配str[4]与str[8]时，明显对不上，但是如果简单地将j=0，那么明显是错的，人的判断应该是前面的cb=结尾的cb，也就是去比较str[1]与str[8]，那么我们要怎么进行比较呢，这就是问题的关键了，那我们的目标就是通过next数组找到str[1]，因为next[7]=4，我们可以肯定的是str[3]=str[7]，而对应的next[3]=1指向了str[0]后面的一位，也就是我们要找的位置，回到我们第一步关于next数组的含义，next[3]=1表示到第四个字符位置，最后缀最长的长度是1，也就是说str[3]=str[0]=str[7]，而这个1也就代表前缀后面的那个字符位置，那么我们通过next[3]不就可以正好找到我们需要的str[1]了，next[3]等于什么，等于next[4-1]，这个4不就是j吗，j=next[j-1]自然就推出来了。抽象开来，只要m = next[j-1]存在非0，那么就存在str[m-1]与str[j-1]相等，也就存在str[m-1]=str[i-1]，就可以保证可以在小前缀中寻找是否存在当前这个长度的字符串的前后缀

第三步，回答第二步的问题。对于next[Y]=X，根据第一步的解释，这句代码的意思是str[Y]=str[X-1]；那么假设next[j-1]非0，且next[j-1]=m，此时代表的是str[j-1]=str[m-1]，而第一轮比较中，比较的是str[i]与str[j]，当进入这个循环时，则代表j>0，也就是说str[j-1]==str[i-1]，而由于这两个值不想等，进行第二轮比较，回溯j的位置，j = next[j-1]，比较的就是str[next[j-1]]与str[i]，也就是str[m]与str[i]，关键来了，为什么可以进行这么比较呢，从next[i]=n->str[i]=str[n-1]，我们可以推出next[j-1]=m->str[j-1]=str[m-1]，那么根据相等的传递性，我们可以最终得出str[m-1]=str[j-1]=str[i-1]，也就可以说明一个非常关键的问题，只要是在回溯j时，找到非0值，就说明待比较字符前面有前缀，所以，这样也可以看出，j = next[j-1];主要的目的就是检查待检查的字符前面是否已经存在部分前缀

第四步，解释kmp搜索算法的这句核心代码的含义。比较两个字符串（str1和str2）中的前后缀，由于i是不停后移的，那么可以反过来看做str1不动，str2后移，而一旦当某个字符匹配不上了，i不动，假设str2此时已经与str1有了部分相同的字符串，也就是j>0，那么就需要做偏移，向前移动j的位置，指向前三步的小前缀的后面一位，而此时i的位置不动，那么就相当于把str2的前缀偏移到str1的相同字符串的后缀；那如果是0的话，就相当于把str2全部偏移，因为前面对上了，但是后面一个对不上，而且，无论从这个字符串的哪个开始都没可能是相同的字符串，将str2的0对齐i；那么，为什么这样操作可以保证是可以正常匹配的，那么就可以举例说明例如两个字符串分别是str1ABCCABD...与str2ABCCABE，当匹配到D与E时，需要将str2后移，显然这时要一口气移动到C后，也就是ABCCAB的后缀上，才能保证str2的前缀AB对上，接着向后遍历

集合覆盖问题（贪心算法）

在对问题进行求解的时候，在每一步选择中都采取最好或者最优的选择，从而能够导致结果是最好或最优的算法，趋近于最优解，要通过条件使其比较更加严格
找出广播电台的组合，能覆盖所有的地区的最少广播电台组合

HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
HashSet<String> hashSet1 = new HashSet<>();
hashSet1.add("北京");
hashSet1.add("上海");
hashSet1.add("天津");
broadcasts.put("k1",hashSet1);

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

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

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

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


HashSet<String> allAddresses = new HashSet<>();
//遍历map中的value中的所有地点
broadcasts.forEach((s, strings) -> strings.forEach(s1 -> allAddresses.add(s1)));
System.out.println(allAddresses);

//存放选择的电台集合
ArrayList<String> selects = new ArrayList<>();

//定义一个临时的集合，在遍历的过程中，存放遍历过程中电台覆盖的地区，和当前没有覆盖的地区的交集
HashSet<String> tempSet = new HashSet<>();

//保存一次遍历过程中，能够覆盖最大的覆盖地区对应的电台的key
//如果maxkey不为空，则加入selects
String maxKey = null;

while (allAddresses.size() != 0) { //如果不为0，则还没有覆盖所有的地区
    //每进行一次循环需要置空maxKey，重新开始找；否则会出现交集大于0，但是小于当前maxKey指向的广播电台覆盖的地区数量
    maxKey = null;
    //遍历 broadcasts
    for (String key : broadcasts.keySet()) {
        //每进行一次for，都要把交集清空，为的是取下一次的交集
        tempSet.clear();
        //获取当前key的广播电台能覆盖的所有地点
        HashSet<String> addresses = broadcasts.get(key);
        tempSet.addAll(addresses);
        //求出tempSet和allAddresses交集 赋给tempSet，就获取了当前的key，可以覆盖的allAddresses当中的地区
        tempSet.retainAll(allAddresses);
        //maxKey == null 指的是还没有找到合适的广播电台，如果此时这个key覆盖的地区与所有的地区有交集了，就可以进行暂存
        //tempSet.size() > broadcasts.get(maxKey).size()
        //这种情况下就说明，经过遍历后新的key的地区与allAddresses的交集，比上一个key的地区与allAddresses的交集还要多，目的是选出每一次遍历的最优解
        if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
            maxKey = key;
        }
    }
    //一次遍历完整，将结果存储
    if (maxKey != null) {
        selects.add(maxKey);
        //将maxKey覆盖的地区从allAddresses去掉
        allAddresses.removeAll(broadcasts.get(maxKey));
    }
}
System.out.println(selects);
复制代码

文章版权归作者所有，未经允许请勿转载。

THE END

后端