题目描述
高中生物中提到,酶切位点 是基因序列上一段特定的碱基序列,而 限制性核酸内切酶 能够识别出这个序列并在对应的切割位置将基因序列切成两段。
现有一种名为 $\texttt{EcoRI}$ 的限制酶,其识别序列为 GAATTC
,切割位置在 G
和 A
之间。
给出一段长度为 $n$ 的基因序列(仅由 A/T/G/C
组成的字符串),请你判断使用 $\texttt{EcoRI}$ 在理想条件下能将此序列切成几个部分,并输出每个切割位置 左侧 碱基的下标。
定义该基因序列的下标从左到右分别为 $1, 2, 3, \dots, n$。
输入格式
第 $1$ 行一个正整数 $n$ 表示基因序列长度。
第 $2$ 行一个长度为 $n$ 的字符串表示基因序列,保证只出现 A/T/G/C
四种字符。
输出格式
第 $1$ 行输出一个正整数 $x$,表示 $\texttt{EcoRI}$ 在理想条件下能将给出序列切成 $x$ 个部分。
第 $2$ 行从小到大输出 $x-1$ 个正整数,表示每个切割位置 左侧 碱基的下标。
样例输入
15
GATCGGAATTCTTCA
样例输出
2
6
样例说明
显然,对于此样例,容易找到 $\texttt{EcoRI}$ 的识别序列和切割位点:$\texttt{GATCG}\color{red}{\texttt{G↓AATTC}}\texttt{TTCA}$。
所以,可以将原基因序列切割成 $2$ 部分,切割位置左侧碱基 G
的下标为 $6$。
数据范围
$6 \le n \le 10^7$
其实就是个 KMP 板子题,已经不能再板子了。(如果不能理解题面,可以看样例说明)