描述

所有的 DNA 序列都是由 'A' , ‘C’ , 'G' , 'T' 字符串组成的，例如 'ACTGGGC' 。
请你实现一个函数找出所有的目标子串，目标子串的定义是，长度等于 10 ，且在 DNA 序列中出现次数超过 1 次的子串（允许两个子串有重合的部分，如下面的示例2所示）。
（注：返回的所有目标子串的顺序必须与原DNA序列的顺序一致，如下面的示例1所示）
数据范围：DNA序列长度满足 1 \le n \le 10^5 \1≤n≤105  ，保证序列中只出现 'A' , 'C' , 'G' , 'T'。

示例1

输入： 
"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
复制
返回值： 
["AAAAACCCCC","CCCCCAAAAA"]
复制
说明： 
"AAAAACCCCC"和"CCCCCAAAAA"长度等于 10 且在DNA序列中分别出现了 2 次。 
不能返回["CCCCCAAAAA","AAAAACCCCC"]，因为在原DNA序列中，"AAAAACCCCC"要比"CCCCCAAAAA"先出现。

示例2

输入： 
"AAAAAAAAAAA"
复制
返回值： 
["AAAAAAAAAA"]
复制
解题思路
1、使用字符串截取函数substr进行逐层截取，当遇到有重复子串时，将重复子串添加到结果串中；
2、这么做会有一个问题，题目要求“返回的所有目标子串的顺序必须与原DNA序列的顺序一致”，判断重复串时该串肯定不是第一次出现，所以不能保证顺序；
3、反过来，从右向左遍历，遍历完后将结果串反转即可得到正确的子串 


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param DNA string字符串 1
     * @return string字符串vector
     */
    vector<string> repeatedDNA(string DNA) {
        // write code here
        int n = DNA.size();
        vector<string> res;
        vector<string> all;
        
        for (int i = n - 10; i >= 0; i--) {
            string tmp = DNA.substr(i, 10);
            //cout << tmp << endl;
            if (find(all.begin(), all.end(), tmp) != all.end()) {
                if (find(res.begin(), res.end(), tmp) == res.end()) {
                    res.push_back(tmp);
                } 
            }
            all.push_back(tmp);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};