-
数据结构与算法(十六)
KMP算法
应用场景-字符串匹配问题
str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好"
str2 = "尚硅谷你尚硅你"
求：str2 在 str1 中是否存在，如果存在，返回第一次出现的位置，如果没有则返回 -1
暴力匹配
假设 str1 匹配到 i 位置，子串 str2 匹配到 j 位置，则：
-
如果当前字符匹配成功（
str1[i] == str2[j]）则
i++、j++继续匹配下一个字符 -
如果失败（
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 个字符进行比较，不符合，关键词（文本串）向后移动一位
-
重复第一步，还是不符合，再后移动
-
一直重复，直到 str1 有一个字符与 str2 的第一个字符匹配为止
-
接着比较字符串和搜索词的下一个字符，还是符合
-
遇到 st1 有一个字符与 str2 对应的字符不符合时
-
这时候：想到的是继续遍历 st1 的下一个字符（也就是暴力匹配）
这时，就出现一个问题：
此时回溯时，A 还会去和 BCD 进行比较，而在上一步 ABCDAB 与 ABCDABD，前 6 个都相等，其中 BCD 搜索词的第一个字符 A 不相等，那么这个时候还要用 A 去匹配 BCD，这肯定会匹配失败。
KMP 算法的想法是：设法利用这个已知信息，不要把「搜索位置」移回已经比较过的位置，继续把它向后移，这样就提高了效率。
那么新的问题就来了：你如何知道 A 与 BCD 不相同，并且只有 BCD 不用比较呢？这个就是 KMP 的核心原理了。
-
KMP 利用 部分匹配表，来省略掉刚刚重复的步骤。
上表是这样看的：
- ABCD 匹配值 0
- ABCDA 匹配值 1
- ABCDAB 匹配值 2
至于如何产生的这个部分匹配表，下面专门讲解，这里你要知道的是，KMP 利用这个 部分匹配表 可以省略掉重复的步骤
-
已知空格与 D 不匹配时，前面 6 个字符
ABCDAB是匹配的。
查表可知：部分匹配值是 2，因此按照下面的公司计算出后移的位数：移动位数 = 已匹配的字符数 - 对应的部分匹配值
- 逐位比较，直到搜索词（文本串）的最后一位，发现完全匹配，搜索完成。
部分匹配表是如何产生的？
看上上述步骤，你现在的疑惑是：这个部分匹配表是如何产生的？下面就来介绍
需要先知道 **前缀 ** 和 后缀 是什么
-
前缀：仔细看，它的前缀就是每个字符串的组合，逐渐变长，但是不包括最后一个字符
如果
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 | "杭州", "大连" |
目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合，思路如下:
-
将所有需要覆盖的地区找出来（allAreas）也就是所有电台中的覆盖地区去重后的列表
-
遍历所有的广播电台，找到一个 覆盖了最多未覆盖的地区 的电台，此电台可能包含一些已覆盖的地区，但是没有关系。
比如：k1 中有三个地区，在上面找出来的列表中去判定是否覆盖其中的地区，找到则 k1 为 覆盖了最多未覆盖的地区 的电台。
-
将这个电台加入到一个集合中（如 ArrayList），并想办法把该电台覆盖的地区在下次比较时去掉。
比如：前面 k1 为 覆盖了最多未覆盖的地区，把 k1 加到该集合中，并从把 k1 已经覆盖过的地区从 allAreas 中移除
-
重复第 2 步，直到覆盖了全部的地区
图解
给定的广播电台如下
| 广播台 | 覆盖地区 |
|---|---|
| K1 | "北京", "上海", "天津" |
| K2 | "广州", "北京", "深圳" |
| K3 | "成都", "上海", "杭州" |
| K4 | "上海", "天津" |
| K5 | "杭州", "大连" |
-
找出所有需要覆盖的地区
allAreas = {"北京", "上海", "天津", "广州", "深圳", "成都", "杭州", "大连"} -
遍历广播电台列表：找出一个覆盖了最多地区的电台，重点：如何确定覆盖了最多的电台？
可以这样做：遍历广播台，计算每个电台中覆盖的地区在未覆盖地区列表中，覆盖了几个？
广播台 覆盖地区 覆盖数量（未覆盖地区的数量） K1 "北京", "上海", "天津" 3 K2 "广州", "北京", "深圳" 3 K3 "成都", "上海", "杭州" 3 K4 "上海", "天津" 2 K5 "杭州", "大连" 2 上图覆盖数量计算，例如：k1 覆盖地区有三个，这三个地区现在都在 未覆盖地区（allAreas），所以：k1 的覆盖数量则是 3
-
找到覆盖数量最大的电台（每一步的选择都选择最优）
上第 2 步骤中，计算出的覆盖数量，k1 为最大的（k2 也是 3，但是不大于 k1 的覆盖数量），计为
maxKey，将它添加到 选择列表中，表示该电台已被选择，同时将 k1 中覆盖地区，从 allAreas 列表中去掉，那么现在的情况就如下：// 已选电台 selects = {"k1"} // 未覆盖地区 allAreas = {广州", "深圳", "成都", "杭州", "大连"} -
重新计算未被选择的电台的覆盖数量
// 已选择电台 selects = {"k1"} // 所有暂时还未覆盖的地区列表 allAreas = {广州", "深圳", "成都", "杭州", "大连"}广播台 覆盖地区 覆盖数量（未覆盖地区的数量） K1 "北京", "上海", "天津" 0 K2 "广州", "北京", "深圳" 2 K3 "成都", "上海", "杭州" 2 K4 "上海", "天津" 0 K5 "杭州", "大连" 2 注意：因为 k1，已经被选择过，可以不重新对它计数，也可以重新计数，对性能影响不太大。
上图覆盖数量计算，例如：
- k1 覆盖地区有三个，这三个地区现在在 未覆盖地区（allAreas）中一个都没有，所以：k1 的覆盖数量则是 0
- k2 覆盖的确有三个，这三个地区现在在 未覆盖地区（allAreas）中有 2 个：广州、深圳，而北京已经被覆盖掉了（k1），所以：k2 的覆盖数量则是 2
-
找到覆盖数量最大的电台,重复上面的过程，直到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，则可解决这个问题。
来源：https://www.cnblogs.com/wyzstudy/p/15449326.html
