力扣labuladong——一刷day23

力扣labuladong——一刷day23"/>

力扣labuladong——一刷day23

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、力扣187. 重复的DNA序列
• 二、力扣28. 找出字符串中第一个匹配项的下标

前言

我们不要每次都去一个字符一个字符地比较子串和模式串，而是维护一个滑动窗口，运用滑动哈希算法一边滑动一边计算窗口中字符串的哈希值，拿这个哈希值去和模式串的哈希值比较，这样就可以避免截取子串，从而把匹配算法降低为 O(N)，这就是 Rabin-Karp 指纹字符串查找算法的核心逻辑。

一、力扣187. 重复的DNA序列

class Solution {public List<String> findRepeatedDnaSequences(String s) {List<String> res = new ArrayList<>();if(s.length() < 10)return res;Map<String,Integer> map = new HashMap<>();int left = 0, right = 9;while(right < s.length()){String cur = s.substring(left,right+1);right ++;map.put(cur,map.getOrDefault(cur,0)+1);left ++;}for(String k : map.keySet()){if(map.get(k) > 1){res.add(k);}}return res;}
}

`在滑动窗口中快速计算窗口中元素的哈希值，叫做滑动哈希技巧`

class Solution {public List<String> findRepeatedDnaSequences(String s) {int[] nums = new int[s.length()];for(int i = 0; i < s.length(); i ++){switch(s.charAt(i)){case 'A':nums[i] = 0;break;case 'C' :nums[i] = 1;break;case 'G' :nums[i] = 2;break;case 'T':nums[i] = 3;break;}}HashSet<Integer> seen = new HashSet<>();HashSet<String> res = new HashSet<>();int R = 4;//进制int L = 10;//当前位数int RL = (int)Math.pow(R,L-1);int windowHash = 0;int left = 0, right = 0;while(right < nums.length){windowHash = windowHash * R + nums[right];right ++;if(right - left == L){if(seen.contains(windowHash)){res.add(s.substring(left,right));}else{seen.add(windowHash);}windowHash = windowHash - nums[left] * RL;left ++;}}return new LinkedList<>(res);}
}

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

class Solution {public int strStr(String haystack, String needle) {int L = needle.length();int R = 256;long LR = 1;long Q = 1658598167;for(int i = 1; i <= L-1; i ++){LR = (LR * R)%Q;}long needleHash = 0;long windowHash = 0;for(int i = 0; i < L; i ++){needleHash = (needleHash * R + needle.charAt(i))%Q ;}int left = 0, right = 0;while(right < haystack.length()){windowHash = ((windowHash * R)%Q + haystack.charAt(right))%Q;right ++;if(right - left == L){if(windowHash == needleHash){if(needle.equals(haystack.substring(left,right))){return left;}}windowHash = (windowHash - (haystack.charAt(left)*LR)%Q+Q)%Q;left ++;}}return -1;}
}