> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/bit-manipulation/hash/repeated-dna-sequences.md).

# Repeated DNA Sequences

<https://leetcode.com/problems/repeated-dna-sequences/description/>

> All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
>
> Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
>
> For example,
>
> ```
> Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
>
> Return:
> ["AAAAACCCCC", "CCCCCAAAAA"].
> ```

## Thoughts

首先这个有歧义，开始一直以为是找No overlapping的重复子数组，看了别人的答案才知道不一定要no overlapping, 比如

If you enter your "AAAAAAAAAAA" as custom test and click "Run Code", you'll see that **expected** answer **is**

\["AAAAAAAAAA"].

知道了这点很容易想出naive 解法。即每次移动一位，把遇到的都记录下来。但这么做浪费空间。

还可以用整数存储方法。

> 这个思路非常简单，这里一共有四个字母：A，C，G，T。我们转换整数的思路如下：
>
> 1. A = 00，C = 01，G = 10，T = 11。
> 2. int key = 0, key = key << 2 | code(A|C|G|T)。