题目描述

所有DNA序列都可以用 A，C，G，T 四个字母表示，比如 "ACGAATTCCG"，研究DNA序列时，有时识别重复子串是很有意义的。

请编写一个程序，找到所有长度为10的且出现次数多于1的子串。

样例

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC", "CCCCCAAAAA"]

算法

(哈希表) $O(n)$

用哈希表记录所有长度是10的子串的个数。
从前往后扫描，当子串出现第二次时，将其记录在答案中。

时间复杂度分析：总共约 $n$ 个长度是10的子串，所以总共有 $10n$ 个字符。计算量与字符数量成正比，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        unordered_map<string, int> S;
        for (int i = 0; i + 10 <= s.size(); i ++ )
        {
            string str = s.substr(i, 10);
            if (S[str] == 1) res.push_back(str);
            S[str] ++ ;
        }
        return res;
    }
};