TopCoder problem "DocumentSearch" used in SRM 349 (Division II Level One)

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 String[] doc into a single string. Then, return the maximum number of non-overlapping occurrences of the String search.

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.



Parameters:String[], String
Method signature:int nonIntersecting(String[] doc, String search)
(be sure your method is public)


-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 (' ').


Returns: 1
The example from the problem statement.
Returns: 2
There are multiple ways to find the string twice, but it doesn't matter how we do it.
Returns: 1
Be sure to concatenate the document first.
{"aaa", "aa", "a", "a"}
Returns: 3

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Simple Search, Iteration, String Manipulation