FrequentSubstring
SRM 853 · 2024-02-21 · by misof
Problem Statement
You are given the
Consider all possible strings of H lowercase English letters. For each of them, determine the number of times needle occurs in it as a contiguous substring. (The occurrences may overlap each other arbitrarily.)
Calculate and return the maximum of all those numbers. In other words, find and return the largest X such that needle can have X occurrences in a string of length H.
Constraints
- needle will contain between 1 and 2,500 characters, inclusive.
- Each character in needle will be a lowercase English letter ('a'-'z').
- H will be between 1 and 10^9, inclusive.
"abc" 5 Returns: 1
There are some strings of length 5 that do not contain the substring "abc": for example, "pqrst" or "axbxc". There are some strings of length 5 that contain the substring "abc" once: for example, "abcde", "xabcx", or "aaabc". There are no strings of length 5 that contain more than one occurrence of the substring "abc", so 1 is the correct answer.
"aaa" 5 Returns: 3
The string "aaaaa" contains three overlapping occurrences of "aaa": one is "aaa--", the second is "-aaa-", and the third is "--aaa".
"ionisation" 19 Returns: 2
"x" 999999997 Returns: 999999997
"abracadabra" 28 Returns: 3
One of the strings of length 28 with exactly three occurrences of "abracadabra" is "abracadabrabracadabracadabra". There are no strings of length 28 with four or more occurrences of "abracadabra".
"toot" 8 Returns: 2
There are some strings of length 8 with two occurrences of "toot". Some of them are "toottoot", "tootootx", and "etootoot". No string of length 8 has more occurrences of "toot".
Submissions are judged against all 90 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FrequentSubstring with a public method int maximize(string needle, int H) · 90 test cases · 2 s / 256 MB per case