시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB1000.000%

문제

In honor of the third anniversary since the International tournament in Shumen became IATI, the organizers have come up with a new interesting game. Deni decided to take part in it. She went to a tablet, where the game was loaded. There was some string w of length N, consisting only of lowercase Latin letters.

The game has Q rounds and each round is as follows: the player thinks of some length m and the most frequently occurring substring s among all substrings of length m or longer is found. The points for a current round are scored by the count of occurrences of s in w and we denote it by cnt. In order to be more interesting, the player gives a length k ≥ m with the intention that the found substring s should not have a length longer than k. Also, the found substring should not be possible to be extended with some letters on the left or on the right so that to obtain a new string of length longer than k which has at least cnt occurrences. In other words, the length of s has to be between m and k and for every possible substring t, so that each of the concatenated strings ts and st, having length more than k, has to have less than cnt occurrences in w. If there is no such substring s, then the scored points for the round are 0.

You have to write the program which will work on the tablets and so our heroine will be satisfied. The program should have the functions start() and round(), which will be compiled with the source file of the jury. For each round your implementation of round() has to return the number of points – the maximum number of occurrences of the wanted substring or 0 if there isn’t any possibility for the current round. The function start() will receive the string, loaded on the tablet. After that the jury program will call Q times the function round() with two integers m and k – the constraints for the wanted substring.

구현

The function start() has the prototype:

void start(char w[]);

It is called once by the program of the jury with one parameter w – the string, loaded on the tablet. The string w is null-terminated, i.e. the string is terminated with the '\0' character. This character is not counted in the length of the string. The other function round(), for processing one round, has the prototype:

int round(int m, int k);

The parameters are the integers that are the constraints for the wanted substring. Here the following conditions hold 1 ≤ m ≤ k ≤ N, where N is the length of the word w. When the function finds the answer for the current round, it has to return one integer – the points for the round.

You have to submit to the system only the file Sgame.cpp, which has the functions start() and round(). This file can contain also other lines of code and functions, needed for your work, but it shouldn’t have the function main().

At the beginning of your file you have to include this line: #include "Sgame.h".

제한

  • 1 ≤ N ≤ 5∙105
  • 1 ≤ Q ≤ 106

서브태스크

번호배점제한
15

N ≤ 103, Q ≤ 10, k = N

27

N ≤ 5∙103, Q ≤ 103, k = N

312

N ≤ 102, Q ≤ 103

418

N ≤ 105, Q ≤ 105, k = N

524

N ≤ 5∙105, Q ≤ 106, We look for extension only on the left of a substring.

634

N ≤ 5∙105, Q ≤ 106

Answers on the tests for the fifth subtask, that meet the conditions in the original statement for the task, are also considered correct!

예제

Let the string w, loaded on the tablet, is abcabcabcdedea and there are 3 rounds. The program of the jury will call your function in this way: start(w). After it finishes its work, the program of the jury will call your function round three times:

Calling function round Correct answer Explanation
round(1,2) 4 The substring with most occurrences is a. Because it can’t be extended on the left or on the right to make a substring with 4 or more occurrences, this substring is the answer.
round(2,3) 3 The substring with most occurrences is ab. It can be extended on the right at most as abc, which also has three occurrences. This is possible because of k = 3. Another possible answer is bc.
round(2,2) 2 Here because k is only 2, neither ab, nor bc are valid answers. That’s why the substring with the most occurrences is de.

로컬 테스팅

You are given the files Lgrader.cpp and Sgame.h for local testing. You have to place them in the same folder as your program Sgame.cpp and you have to compile the file Lgrader.cpp. In such a way, you will make a program to check the correctness of your functions. The program will require the following sequence of data from the standard input:

  • on the first line: the string w.
  • on the second line: one positive integer
  • the number of rounds Q.
  • on the last Q lines: on each line, there have to be two positive integers – the length m and the length k for each round.

The output of the program will be Q integers – the points that you find for each round.

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.