AIOC Banner

Problem: Memes

Want to try solving this problem? You can submit your code online if you log in or register.


Memes

Time Limit: 1.5 seconds
Memory Limit: 128 MB
Input: stdin
Output: stdout

You like Internet memes. Like that video with the people dancing! Or that picture of the animal giving silly advice. Or that movie reference that people are always using on the image boards. These are all highly specific Internet memes, which you like a lot, because - as mentioned above - you like Internet memes.

After extensive analysis of the transcripts of hundreds of thousands of videos and captioned images, you have discovered that the key to a successful Internet meme consists of two simple ingredients:

For example, "beaver" is not a valid critical string, since it contains more than one "e". But the "badger" is valid!

Given the critical string "badger", we can then analyse the following text (larger string):

snakebadgerbadgertigertigertigerbadgerbadllamaduck

As you can see, the critical string ("badger") appears 3 times in total in the text. The longest run of consecutive critical strings is of length 2 in "badgerbadger" (indices 6 through 17 inclusive).

By changing a few characters (the ones at indices 27,28,29,42,43,44) we get the following new text:

snakebadgerbadgertigertigebadgerbadgerbadgermaduck

Now the critical string appears 5 times, and its longest consecutive run is 3 times in a row.

Your task is to write a program that analyses a text for the number of critical string occurences and the length of the longest run of critical strings. Furthermore, it must determine this after each change in a sequence of one-character changes to the text.

Input

Output

Your program should produce Q lines of output: one for each update made to the text.

The ith line should contain two space-separated integers αi and βi , where:

Sample Input

6 50
98 97 100 103 101 114
115 110 97 107 101 98 97 100 103 101 114 98 97 100 103 101 114 116 105
   103 101 114 116 105 103 101 114 116 105 103 101 114 98 97 100 103 101
   114 98 97 100 108 108 97 109 97 100 117 99 107
6
27 98
28 97
29 100
42 103
43 101
44 114

Sample Output

3 2
3 2
4 2
4 2
4 2
5 3

Explanation

The sample input corresponds to the example described above (with characters replaced by their ASCII integer equivalents). Note however that for page space reasons, we have separated B into multiple lines, but in the input file it it will occupy only one line.

Subtasks & Constraints

For each subtask, your program will score 40% of the available marks if all αi values are correct, and 60% of the available marks if all βi values are correct.

 


Privacy statement
© Australian Mathematics Trust 2001-2024

Contact: training@orac.amt.edu.au
Page generated: 29 March 2024,  1:32am AEDT