lc187. 重复的DNA序列（字符串哈希）

所有 DNA 都由一系列缩写为 ‘A’，’C’，’G’ 和 ‘T’ 的核苷酸组成，例如：”ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

示例 1：

输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输出：[“AAAAACCCCC”,”CCCCCAAAAA”]
示例 2：

输入：s = “AAAAAAAAAAAAA”
输出：[“AAAAAAAAAA”]

提示：

0 <= s.length <= 105
s[i] 为 ‘A’、’C’、’G’ 或 ‘T’

class Solution {
    /**
    本题使用字符串哈希+哈希表的方式求解，先对s进行前缀和哈希
    再遍历每个以i开始长度为10 的字符串哈希值，为了去重，我们之加入map中值为1的字符串
     */
    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
         //P一般取131或13331，取模Q一般是2^64，所以我们只用long就行，溢出就相当于取模了
        int P = 131;
        //h数组表示s的前缀和哈希，p数组时表示P进制
        long[] h = new long[n+10], p = new long[n+10];
        p[0] = 1;
        for (int i = 0; i < n; ++i) {
            p[i+1] = p[i] * P;
            h[i+1] = h[i] * P + s.charAt(i);
        } 
        Map<Long,Integer> map = new HashMap<>();
        List<String> res = new ArrayList<>();
        for (int i = 0; i + 10 - 1 < n; ++i) {
            int j = i+10-1;
            //因为是从0开始遍历，h，p都是下标1开始的
            //hash = h[j] - h[i-1] * p[j-i+1];
            long hash = h[j+1] - h[i] * p[j-i+1];
            int count = map.getOrDefault(hash,0);
            //去重
            if (count == 1) res.add(s.substring(i,j+1));
            map.put(hash,count+1);
        }
        return res;
    }
}