Connection Status:
Competition Arena > SubstringCoverage

SubstringCoverage

SRM 853 · 2024-02-21 · by misof

SRM 853 · 2024-02-21 · by misof · Dynamic Programming, Graph Theory, String Manipulation
Class Name: SubstringCoverage
Return Type: int
Method Name: count
Arg Types: (string, int)
Problem Statement

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.

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
0)
"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.

1)
"abracadabra"
24
Returns: 4
2)
"coco"
20
Returns: 9
3)
"abracadabra"
10
Returns: 0
4)
"abracadabra"
11
Returns: 1

Submissions are judged against all 97 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SubstringCoverage with a public method int count(string needle, int H) · 97 test cases · 2 s / 256 MB per case

Submitting as anonymous