MostSubstrings
SRM 806 · 2021-05-24 · by misof
Problem Statement
Let C(Haystack, Needle) be the number of different (possibly overlapping) occurrences of the string Needle in the string Haystack as a contiguous substring.
For example, C("ababababa", "aba") = 4, C("cat", "catastrophy") = 0, and C("canyoudancecancan", "can") = 3.
Given is a string S of lowercase English letters and an
Let Cmax be the largest possible number of times S may occur in a string of length L. In other words, Cmax is the maximum value of C(T, S) taken over all strings T of length L.
Count all strings T made of exactly L lowercase English letters such that C(T, S) = Cmax. Return their count modulo 10^9 + 7.
Constraints
- S will have between 1 and 100 characters, inclusive.
- Each character of S will be a lowercase English letter.
- L will be between 1 and 1000, inclusive.
"helloworld" 7 Returns: 31810120
Each of the 26^7 possible strings of length 7 contains 0 occurrences of the string "helloworld", so each of them is optimal. The return value is (26^7 modulo (10^9 + 7)).
"aaaa" 13 Returns: 1
The only optimal string is "aaaaaaaaaaaaa" (13 'a's).
"dogecoin" 17 Returns: 78
The optimal answers are strings of the form "Xdogecoindogecoin", "dogecoinXdogecoin", and "dogecoindogecoinX", where X can be any single letter.
"decode" 11 Returns: 52
Now the optimal solutions are strings of the form "Xdecodecode" and "decodecodeX".
"abadeaba" 8 Returns: 1
Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MostSubstrings with a public method int count(string S, int L) · 87 test cases · 2 s / 256 MB per case