Problem Statement
Given two strings S and T, an occurrence of S in T is a contiguous substring of T that exactly matches S.
The string T is covered by occurrences of S if each character of T is a part of one or more occurrences of S in T.
For example, the string T1 = "ababaaba" is covered by occurrences of S = "aba" but the string T2 = "abaaaba" isn't because the middle letter of T2 isn't in any occurrence of S in T2.
You are given the String needle that consists of lowercase English letters ('a'-'z') only.
The length X is called coverable if there is a String of length exactly X that is covered by occurrences of needle.
Given needle and an int H, for each length from 1 to H inclusive determine whether it's coverable, and return the total number of coverable lengths in this range.
Definition
- Class:
- SubstringCoverage
- Method:
- count
- Parameters:
- String, int
- Returns:
- int
- Method signature:
- int count(String needle, int H)
- (be sure your method is public)
Constraints
- needle will have between 1 and 5,000 characters, inclusive.
- Each character of needle will be a lowercase English letter ('a'-'z').
- H will be between 1 and 10^9, inclusive.
Examples
"abc"
11
Returns: 3
Out of all possible strings of all lengths up to 11, only three are covered by the substring "abc". These are the strings "abc", "abcabc", and "abcabcabc". Thus, there are three coverable lengths in the given range."abracadabra"
24
Returns: 4
"coco"
20
Returns: 9