时间限制： 4s
空间限制： 512MB

题目类型说明

这是一道提交函数题。

你需要实现两个函数：

void start(char w[]);
int round(int m, int k);

评测程序会先调用一次 start，随后调用多次 round。你只需提交 Sgame.cpp，不能编写 main 函数。

题目描述

给定一个仅由小写英文字母组成的字符串 w，长度为 N。

游戏共有 Q 轮。每一轮给定两个整数 m, k，满足 1 <= m <= k <= N。

你需要考虑某个子串 s，它必须满足：

• m <= |s| <= k；
• 设 cnt 为 s 在 w 中出现的次数，则 cnt 要尽可能大；
• 并且 s 不能被继续向左或向右扩展成一个长度**大于 k**的新串 usv，同时这个新串在 w 中的出现次数仍然不少于 cnt。

更形式化地说，若 s 被选为答案，设其出现次数为 cnt，则对任意使得 |usv| > k 的字符串 usv，它在 w 中的出现次数都必须严格小于 cnt。

如果不存在满足条件的子串，则这一轮答案为 0。

你需要在每次 round(m, k) 调用中返回本轮的最大得分，即满足条件的子串出现次数的最大值；若不存在则返回 0。

你需要实现的函数

void start(char w[])

该函数会被调用一次，参数 w 是待处理字符串，以空字符 '\0' 结尾。

你可以在这里进行预处理。

int round(int m, int k)

该函数会被调用 Q 次。

对于当前给定的 m, k，你需要返回本轮答案。

提交要求

你只需要提交文件 Sgame.cpp，其中必须包含：

• start
• round

以及你自己实现的其他辅助函数或变量。

你的代码中：

• 必须包含 #include "Sgame.h"
• 不能包含 main 函数

本地测试

题目提供 Lgrader.cpp 与 Sgame.h 供本地调试。

@头文件

@交互文件

本地评测输入格式为：

• 第一行：字符串 w
• 第二行：整数 Q
• 接下来 Q 行：每行两个整数 m, k

本地评测输出为 Q 行，每行一个整数，表示对应询问的答案。

数据范围

• 1 <= N <= 5 × 10^5
• 1 <= Q <= 10^6

子任务

注：原题说明中，第 5 子任务按“只能向左扩展”的旧版叙述给出；但满足原题完整要求的做法同样会被接受。

样例交互说明

设字符串 w = "abcabcabcdedea"，共有 3 轮。

评测程序先调用：

start(w);

随后依次调用：