AdditionalFile6996.zip

#6996. 「THUPC 2026 初赛」回响形态

标签: 传统 | 时间限制: 500 ms | 内存限制: 1024 MiB |

题目描述

请注意本题特殊的时间限制。

给定一个长为 $n$ 的串 $s$ 。称子串 $s[i \ldots j]$ 的中心是 $\frac{i+j}{2}$。

现在你要回答 $q$ 次询问，每次询问给出一个 $k$ ，问所有中心为 $\frac{k}{2}$ 的子串的 border 个数之和。

border 的定义如下：一个非空字符串 $t$ 是另一个字符串 $s$ 的 border，当且仅当 $t$ 既是 $s$ 的前缀，也是 $s$ 的后缀。例如，对任一个非空字符串 $s, s$ 本身就是一个 $s$ 的 border。

输入格式

从标准输入读入数据。

第一行包含两个正整数 $n$ $\left(1 \leq n \leq 10^{6}\right), q$ $\left(1 \leq q \leq 20\right)$ ，表示输入字符串 $s$ 的长度及询问次数。

第二行包含一个长度为 $n$ 的字符串 $s$ ，由英文小写字母组成。

接下来 $q$ 行，每行一个整数 $k$ $\left(2 \leq k \leq 2 n\right)$ ，表示一组询问。

输出格式

输出到标准输出。

输出 $q$ 行，第 $i$ 行表示第 $i$ 个询问的答案。

样例 1

输入

9 6
bbabbbbaa
2
5
10
11
14
15

输出

1
3
8
9
3
2

当 $k=2$ 时，以 $k / 2$ 为中心的子串只有 $s[1 \ldots 1]=b$，border 数为 $1$。

当 $k=5$ 时，以 $k / 2$ 为中心的子串有 $s[2 \ldots 3]=ba, s[1 \ldots 4]=bbab$，border 数分别为 $1,2$。

当 $k=10$ 时，以 $k / 2$ 为中心的子串有 $s[5 \ldots 5]=b, s[4 \ldots 6]=bbb, s[3 \ldots 7]= abbbb, s[2 \ldots 8]=babbbba, s[1 \ldots 9]=bbabbbbaa$，border 数分别为 $1,3,1,2,1$。

题目使用协议

来自 THUPC2026（2026年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2026 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2026pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。