DocumentSearch
SRM 349 · 2007-05-15 · by erinn
Problem Statement
You have been tasked with writing a function that will scan through a given document, and determine how many times a given word or phrase appears in that document. However, it is important that your function does not count overlapping occurrences. For instance, if the document were "abababa", and the search keyword was "ababa", you could find the keyword starting at index 0, or at index 2, but not both, since they would overlap.
You must concatenate the elements of the given
To find a maximal set of non-overlapping occurrences, perform the following procedure. Starting from the left, find the first occurrence of the search string. Then, continuing with the character immediately following the search string, continue looking for the next occurrence. Repeat until no new occurrences can be found. By continuing immediately following each found occurrence, we guarantee that we will not count overlaps.
Constraints
- doc will contain between 1 and 50 elements, inclusive.
- Each element of doc will contain between 1 and 50 characters, inclusive.
- Each character of each element of doc will be a lowercase letter ('a'-'z') or a space (' ').
- search will contain between 1 and 50 characters, inclusive.
- Each character of search will be a lowercase letter ('a'-'z') or a space (' ').
{"ababababa"}
"ababa"
Returns: 1
The example from the problem statement.
{"ababababa"}
"aba"
Returns: 2
There are multiple ways to find the string twice, but it doesn't matter how we do it.
{"abcdefghijklmnop",
"qrstuvwxyz"}
"pqrs"
Returns: 1
Be sure to concatenate the document first.
{"a"}
"ab"
Returns: 0
{"a", "a", "a", "a", "a", "a", "a"}
"a"
Returns: 7
Submissions are judged against all 49 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DocumentSearch with a public method int nonIntersecting(vector<string> doc, string search) · 49 test cases · 2 s / 256 MB per case