Author: | A. Klenin | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
Many compression algorithms are based on finding frequently repeating substrings in the input data. Since it is often impractical to search the whole input for repetitions, only a limited compression window is considered on each step.
While researching a new compression algorithm, young computer scientist Vasya encountered the following problem.
Given input string of N bits, let the compression window be any substring of M bits. Inside each compression window, find the maximum number of occurrences of any substring of length L (L≤M).
In the sample input 1 below, compression window length is equal to string length, so there is only a single window. Most frequent substring of length 2 is 01, which occurs 5 times.
First line of input file contains integers LM. Second line input file contains a string of length N, each character either 0 or 1.
Output file must contain N−M+1 integers — maximum substring frequencies for each compression window.
1≤M≤N≤2×105, 1≤L≤100
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|