USACO 2024 US Open Contest, Silver - Problem 3: The 'Winning' Gene

注意：此问题的内存限制为512MB，是默认值的两倍。

问题描述

多年来举办比赛并看着Bessie一次又一次获得第一名后，Farmer John意识到这不可能是偶然的。相反，他得出结论，Bessie的DNA中一定编码了“获胜”基因，于是他着手寻找这个“获胜”基因。

他设计了一个过程来确定这个“获胜”基因的可能候选者。他获取Bessie的基因组，这是一个长度为$N$（$1 \leq N \leq 3000$）的字符串$S$。他选择一些数对$(K, L)$，其中$1 \leq L \leq K \leq N$，表示“获胜”基因候选者的长度为$L$，并且将在长度为$K$的较大子串中找到。为了识别基因，他从$S$中取出所有长度为$K$的子串（我们称之为$k$-mer）。对于给定的$k$-mer，他取出所有长度为$L$的子串，确定字典序最小的子串作为获胜基因候选者（如果有平局则选择最左边的子串），然后将该子串在$S$中的0索引位置$p_i$写入集合$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)$对数，每个数字占一行。

示例输入

8
AGTCAACG

示例输出

11
10
5
4
2
2
1
1

解释

在这个测试用例中，输出的第三行是5，因为我们看到恰好有5对$K$和$L$允许有三个“获胜”基因候选者。这些候选者（其中$p_i$是0索引）为：

• $(4,2) \to P = [0,3,4]$
• $(5,3) \to P = [0,3,4]$
• $(6,4) \to P = [0,3,4]$
• $(6,5) \to P = [0,1,3]$
• $(6,6) \to P = [0,1,2]$

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

AGTC
GTCA
TCAA
CAAC
AACG

对于每个4 - mer，我们确定字典序最小的长度为2的子串：

AGTC -> AG
GTCA -> CA
TCAA -> AA
CAAC -> AA
AACG -> AA

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

另一方面，如果我们关注数对$(4,1)$，我们看到这只会导致总共2个“获胜”基因候选者。如果我们取所有4 - mer并确定字典序最小的长度为1的子串（使用$A$、$A'$和$A*$来区分不同的$A$），我们得到：

AGTC -> A
GTCA' -> A'
TCA'A* -> A'
CA'A*C -> A'
A'A*CG -> A'

虽然在最后三种情况下$A'$和$A*$在字典序上都是最小的，但最左边的子串优先，所以在所有这些情况下$A'$被计为唯一的候选者。这意味着$P = [0, 4]$。

评分

• 输入2 - 4：$N \leq 100$
• 输入5 - 7：$N \leq 500$
• 输入8 - 16：无额外限制。

问题提供者：Suhas Nagar