4040. [USACO24 Open Silver]The 'Winning' Gene

【题目描述】

在多年举办比赛并看着 $Bessie$ 一次又一次地获得第一名后，$FJ$ 意识到这绝非偶然。他得出结论，$Bessie$ 一定将胜利写进了 DNA，于是他开始寻找这种「胜利」基因。

他设计了一个过程来识别这个「胜利」基因的可能候选。他获取了 $Bessie$ 的基因组，为一个长为 $N$ 的字符串 $S$，其中 $1\le N\le 3000$。他选择某个数对 $(K,L)$，其中 $1\le L\le K\le N$，表示「胜利」基因候选的长度将为 $L$，并且将在一个较大的 $K$ 长度子串中进行寻找。为了识别这一基因，他从 $S$ 中取出所有 $K$ 长度的子串，我们将称这样的子串为一个 $K$-mer。对于一个给定的 $K$-mer，他取出其所有长度为 $L$ 的子串，将字典序最小的子串识别为胜利基因候选（如果存在并列则选择其中最左边的子串），然后将该字串在 $S$ 中的起始位置 $p_i$（从 $0$ 开始索引）写入一个集合 $P$。

由于他还没有选定 $K$ 和 $L$，他想知道每对 $(K,L)$ 将有多少个候选。

对于 $1\ldots N$ 中的每一个 $v$，帮助他求出满足 $|P|=v$ 的 $(K,L)$ 对的数量。

【输入格式】

输入的第一行包含 $N$，为字符串的长度。第二行包含 $S$，为给定的字符串。输入保证所有字符均为大写字符，其中 $s_i\in  A-Z$，因为奶牛遗传学远比我们的高级。

【输出格式】

对于 $1\ldots N$ 中的每一个 $v$，输出满足 $|P|=v$ 的 $(K,L)$ 对的数量，每行输出一个数。

【样例1输入】

8
AGTCAACG

【样例1输出】

11
10
5
4
2
2
1
1

【样例1说明】

在这个测试用例中，输出的第三行为 $5$ 是因为我们发现恰好有 $5$ 对 $K$ 和 $L$ 存在三个「胜利」基因候选。这些候选为（其中 $p_i$ 从 $0$ 开始索引）：

$(4,2) \Rightarrow P = [0,3,4]$

$(5,3) \Rightarrow P = [0,3,4]$

$(6,4) \Rightarrow P = [0,3,4]$

$(6,5) \Rightarrow P = [0,1,3]$

$(6,6) \Rightarrow P = [0,1,2]$

为了了解 $(4,2)$ 如何得到这些结果，我们取出所有的 $4$-mer

$AGTC$

$GTCA$

$TCAA$

$CAAC$

$AACG$

对于每一个 $4$-mer，我们识别出字典序最小的长度为 $2$ 的子串

$AGTC \Rightarrow AG$

$GTCA \Rightarrow CA$

$TCAA \Rightarrow AA$

$CAAC \Rightarrow AA$

$AACG \Rightarrow AA$

我们取出所有这些子串在原字符串中的位置并将它们添加到集合 $P$ 中，得到 $P=[0,3,4]$。

另一方面，如果我们关注 $(4,1)$ 对，我们会发现这只会得到总共 $2$ 个「胜利」基因候选。如果我们取出所有的 $4$-mer 并识别字典序最小的长度为 $1$ 的子串（用 $A$，$A'$ 和 $A*$ 来区分不同的 $A$），我们得到

$AGTC \Rightarrow A$

$GTCA' \Rightarrow A'$

$TCA'A* \Rightarrow A'$

$CA'A*C \Rightarrow A'$

$A'A*CG \Rightarrow A'$

尽管 $A'$ 和 $A*$ 在最后 $3$ 种情况下字典序均为最小，但最左边的子串优先，因此仅有 $A'$ 在所有这些情况中被视为候选。这意味着 $P=[0,4]$。

【样例2输入输出】

点击下载样例2

【数据规模与约定】

- 测试点 $1-3$：$N\le 100$。

- 测试点 $4-6$：$N\le 500$。

- 测试点 $7-15$：没有额外限制。

【来源】

USACO