FrequentSubstring | Topcoder Archive

Problem Statement

You are given the String needle that consists of lowercase English letters ('a'-'z') only.

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.

Definition

Class:: FrequentSubstring
Method:: maximize
Parameters:: String, int
Returns:: int
Method signature:: int maximize(String needle, int H)
(be sure your method is public)

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.

Examples

```
"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".
```
"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".
```
"abracadabra"
```
```
3
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.