刷题笔记17——KMP

所谓理解，通常不过是误解的总和。——村上春树 《斯普特尼克恋人》

再说一遍！ 去重用哈希

KMP问题

• 靠记忆自己推导了一遍，我对KMP的认知就是一个子串在一个长串上进行滑动，正常去匹配的话就一个一个去遍历就好了，KMP就是一种加速子串移动的方法，如何加速呢？就是跳过根本不可能的情况（利用已经有的信息，将不可能的情况直接排除跳过），目前我们已经有的信息就是长串的i到j，能够和子串的a到b完全匹配，但是到了下一位就不匹配了，那么能从已知的部分匹配中得到什么信息呢？
• 首先我们先假设子串向右挪动一位（这里我们只是假设挪动，看下这次挪动是否有意义），挪动一位后，此时子串的第一位a和长串的第二位i+1对准，a+1和i+2对齐，直到我们刚才失败的那一位，如果这些能匹配上的话，那就太好了，我们又发现一条新的接近ac的路，那就探索下去吧，但是这个匹配条件是否满足呢？这条路是否值得探索呢？我们由之前信息已知，a和i是相等的，那么a和i+1也能匹配的上的条件就是i=i+1，因此我们滑动一步就需要判断一下，新的子串和对应位置长串的值是否相等
• 但是如果这样的话（即需要滑动一步，去判断a和i 的关系， a和i+1的关系来看是否匹配），那么为什么不直接探索i和i+1的关系呢，也就是在滑动之前，先看看已经匹配这一段串的是否具备某些特征，如果说我们直接能推导判断出来，那么就可以避免无效的子串挪动，让子串一步到位。
• 那么如何通过已经匹配的这一段来推导是否需要挪动，帮助子串直接跳到最值得探索的区域？按我们之前说的那种接近ac的路，是需要子串新到达滑动位置的开头到失败位置之前，和对应的长串匹配，那么就是值得探索的，否则的话就直接跳过。
• 那么需要满足子串新到达滑动位置的开头到失败位置之前（假设为A），和对应的长串匹配同时也是子串旧的滑动位置结尾部分(假设为B)，A==B，而我们根据上次的匹配信息可知，A =子串旧的滑动位置开头部分，因此满足条件子串旧的滑动位置开头部分 = B，那么满足 子串旧的滑动位置开头部分 = 子串旧的滑动位置结尾部分，也就是这种格式 abcd……abcd
• 因此只需要提前将子串的每一位置的最长（不知道叫啥名）的匹配提前记录下来，每次遇到就直接滑动到对应位置，就可以加快了，类似dp

2240. 买钢笔和铅笔的方案数

• 间隙做了一道模拟题，完全忽略了给的框架的返回值就必须是long类型

class Solution {
    public long waysToBuyPensPencils(int total, int cost1, int cost2) {
        if(cost1>cost2){
            return waysToBuyPensPencils(total,cost2,cost1);
        }

        int c2 = 0; long res = 0;
        while(c2*cost2<=total){
            res += Math.floor((total-c2*cost2)/cost1) + 1;
            c2++;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 哈希
cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);
substring() 是小写
1
2
3

187. 重复的DNA序列

不需要用KMP，直接s.substring(i,i+10); 即可

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Map<String, Integer> hash = new HashMap<String,Integer>();
        List<String> map = new LinkedList<>();

        for(int i=0;i+9<s.length();i++){
            String temp = s.substring(i,i+10);
            hash.put(temp,hash.getOrDefault(temp,0)+1);
            if(hash.get(temp)==2){
                map.add(temp);
            }
        }
        return map;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

28. 找出字符串中第一个匹配项的下标

class Solution {
    public int strStr(String haystack, String needle) {
        Map<String, Integer> hash = new HashMap<>();
        hash.put(needle,hash.getOrDefault(needle,0)+1);
        for(int i=0;i+needle.length()<=haystack.length();i++){
            String s = haystack.substring(i,i+needle.length());
            hash.put(s,hash.getOrDefault(s,0)+1);
            if(hash.get(needle)>1){
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14