bloggoSequenceSearch

SRM 214 · 2004-10-06 · by Eeyore

SRM 214 · 2004-10-06 · by Eeyore · Search, String Manipulation, String Parsing

Show categories

Class Name: bloggoSequenceSearch

Return Type: String[]

Method Name: findPassages

Arg Types: (vector<string>, string)

Problem Statement

Bloggo lets content producers integrate a text-search facility into their weblogs, making it easy for end users to sift through archival content. One type of query offered by the bloggo search engine is the sequence search. In such a query, consecutive words are separated by an ellipsis, "...". The query matches strings in which all words of the query appear, in the same order as they are given in the query. Such a string, called a passage, begins with the first word of the query and ends with the last word of the query. For example, the sequence-search query


  with...here...there

matches the following passages.


  With a quack-quack here and a quack-quack there

  With an oink-oink here and an oink-oink there

  With a moo-moo here and a moo-moo there

Observe that matching is not case-sensitive. Also bear in mind that words are defined as sequences of alphabetic characters, 'a' to 'z' and 'A' to 'Z', that are not included in a longer word. Thus, the query shown above does not match either of the following passages in part or in whole.


  without a woof-woof here or a woof-woof there

  with a meow-meow here and a meow-meow thereabouts

In the special case of a single-word query, a matching passage is also one word long. The query


  pudding

therefore matches passages that look like this.


  pudding

In general, a query word must appear in a matching passage at least as many times as it appears in the query. Thus, the query


  a...quack...quack...night

does not match


  a quack in the night

but it does match both of the following.


  a quack in the quack factory at night

  a quack doctor said quack quack last night

You are given a String[], documents, each element of which contains a single document. A document may include, in addition to words and spaces, the punctuation symbols ',', ';', '.', '!', '?', '-', '(', and ')'. You are also given a String, query, consisting of one or more words separated by ellipses. Find the top five passages matching this query and return them in a String[] formatted according to the specifications below and sorted by descending order of quality, where quality is also defined below. Each passage must be a substring of an element of documents, and must begin and end with a whole word.

The shorter a passage, the higher its quality. The length of a passage is counted in characters, and a passage extends from the first character of the first query word to the last character of the last query word. If two passages are equally long, the one drawn from the lower-numbered document takes precedence. In the case of equally long passages in the same document, earlier ones are better. Passages may overlap. If there are fewer than five matching passages among the documents, return the ones that do exist. To make the search results helpful to users, each passage should be presented in the format


  DOC_ID START_INDEX [PASSAGE_TEXT]

where DOC_ID is the zero-based index of the document from which the passage is drawn, START_INDEX is the zero-based character index of the first character in the passage, and PASSAGE_TEXT is the text of the passage. There is one space between DOC_ID and START_INDEX, one space between START_INDEX and the left bracket, and no other spaces except possibly in the PASSAGE_TEXT.

Constraints

documents contains between 1 and 50 elements, inclusive
each element of documents is between 1 and 50 characters long, inclusive
the only characters allowed in documents are 'a' to 'z', 'A' to 'Z', the space character, ',', ';', '.', '!', '?', '-', '(', and ')'
query is between 1 and 50 characters long, inclusive
query consists of a sequence-search query as defined above

Examples

{"But in a larger sense we can not dedicate --",
 "we can not consecrate -- we can not hallow this",
 "ground. The brave men, living and dead, who",
 "struggled, here, have consecrated it far above",
 "our poor power to add or detract. The world will",
 "little note, nor long remember, what we say here,", 
 "but can never forget what they did here. It is",
 "for us, the living, rather to be dedicated here",
 "to the unfinished work which they have, thus",
 "far, so nobly carried on. It is rather for us",
 "to be here dedicated to the great task remaining", 
 "before us -- that from these honored dead we take",
 "increased devotion to that cause for which they",
 "here gave the last full measure of devotion --",
 "that we here highly resolve that these dead",
 "shall not have died in vain; that this nation",
 "shall have a new birth of freedom; and that",
 "this government of the people, by the people,", 
 "for the people, shall not perish from the earth."}
"the...People"
Returns: { "17 19 [the people]",  "17 34 [the people]",  "18 4 [the people]",  "17 19 [the people, by the people]" }

These documents are fragments of the Gettysburg Address. Observe that word matching is case-insensitive and that passages may overlap.

{"But in a larger sense we can not dedicate --",
 "we can not consecrate -- we can not hallow this",
 "ground. The brave men, living and dead, who",
 "struggled, here, have consecrated it far above",
 "our poor power to add or detract. The world will",
 "little note, nor long remember, what we say here,", 
 "but can never forget what they did here. It is",
 "for us, the living, rather to be dedicated here",
 "to the unfinished work which they have, thus",
 "far, so nobly carried on. It is rather for us",
 "to be here dedicated to the great task remaining", 
 "before us -- that from these honored dead we take",
 "increased devotion to that cause for which they",
 "here gave the last full measure of devotion --",
 "that we here highly resolve that these dead",
 "shall not have died in vain; that this nation",
 "shall have a new birth of freedom; and that",
 "this government of the people, by the people,", 
 "for the people, shall not perish from the earth."}
"Shall...The"
Returns: { "18 16 [shall not perish from the]" }

Note that the substring "the people, shall" in the last document does not match this query.

{"But in a larger sense we can not dedicate --",
 "we can not consecrate -- we can not hallow this",
 "ground. The brave men, living and dead, who",
 "struggled, here, have consecrated it far above",
 "our poor power to add or detract. The world will",
 "little note, nor long remember, what we say here,", 
 "but can never forget what they did here. It is",
 "for us, the living, rather to be dedicated here",
 "to the unfinished work which they have, thus",
 "far, so nobly carried on. It is rather for us",
 "to be here dedicated to the great task remaining", 
 "before us -- that from these honored dead we take",
 "increased devotion to that cause for which they",
 "here gave the last full measure of devotion --",
 "that we here highly resolve that these dead",
 "shall not have died in vain; that this nation",
 "shall have a new birth of freedom; and that",
 "this government of the people, by the people,", 
 "for the people, shall not perish from the earth."}
"wE...nOT"
Returns: { "0 22 [we can not]",  "1 0 [we can not]",  "1 25 [we can not]",  "1 0 [we can not consecrate -- we can not]" }

{"But in a larger sense we can not dedicate --",
 "we can not consecrate -- we can not hallow this",
 "ground. The brave men, living and dead, who",
 "struggled, here, have consecrated it far above",
 "our poor power to add or detract. The world will",
 "little note, nor long remember, what we say here,", 
 "but can never forget what they did here. It is",
 "for us, the living, rather to be dedicated here",
 "to the unfinished work which they have, thus",
 "far, so nobly carried on. It is rather for us",
 "to be here dedicated to the great task remaining", 
 "before us -- that from these honored dead we take",
 "increased devotion to that cause for which they",
 "here gave the last full measure of devotion --",
 "that we here highly resolve that these dead",
 "shall not have died in vain; that this nation",
 "shall have a new birth of freedom; and that",
 "this government of the people, by the people,", 
 "for the people, shall not perish from the earth."}
"we...can...not"
Returns: { "0 22 [we can not]",  "1 0 [we can not]",  "1 25 [we can not]",  "1 0 [we can not consecrate -- we can not]" }

{"b C a a a B c A A c b b b a a c a c B a B B B B c ",
 "c A B C C A c C A a C c b c c a B C A A C a b b C ",
 "c B A c c C b B C c a A C a b b A b A B B a c a a ",
 "b c c a b a a c C a a A b a B b A b b a C C A A B ",
 "c A C A C a C C b b C C B a c a c B b b a C b C A ",
 "c c a a A C b C A C a c C b a C B A A a B a a C A ",
 "A C C c a a b C B C C A C a b C c b C B A C A A B ",
 "C B c c C A C B a b A A b a C a b b C b b c b C C ",
 "c B c B C B C b a c B a b A a b a B B A C B A A c ",
 "A C C c B B C C B A b B C A a b B B c A c C b A C ",
 "A B C b a A C B B B B c B C A b B b a A a A b c B ",
 "B b b b A B a C a b C C C B c c a A b a c C C c a ",
 "c C A c B a A B b c A B a c b c A a C a C a c B c ",
 "A b c b a c A b A B A B A B a a A B a A A b C c c ",
 "b b a B b a C B B C c C c A c b c b B B C a c b c ",
 "C C B a a C C A A C b b c B b B b a B C C B a c a ",
 "C b a b B A b A A A b a a c A C B b C b a B B a C ",
 "b c A C B c b A B A A c C b B B c A C A B C b B c ",
 "b c A c B a A B c C A C c b c a c A A b A A A B C ",
 "C c c A c B c A B B B A b c c C a c b C b C A C C ",
 "B B C A a c A c A A B a b A B c b c c A B A c C b ",
 "c a B c A b B a a c C c c A A a B A a C C C B c a ",
 "A a a A b C a A b b b B B a a b C b a A A b b c A ",
 "C C c a b A b B a C a b A a A b A C a b A B A A B ",
 "B A a B c b C C b A B C b b A a c b A a b c a a B ",
 "b B a c b C A a C b B B A a B c c b c b B A c c B ",
 "a a b A C C B b b a a a A b c B B b B a c b A C c ",
 "c b B b b A c C A A A B b B A A c A b a c C a b a ",
 "A A b a a c A a A C c b B B B a a c c b B b A c b ",
 "B A C C a b C a A c c c A C A a c a A a C C B C C ",
 "c b b B B B a B c C C b C B b C c B b c b c B c a ",
 "c b C C C A B a A a b c c B C A a b a b C C B B A ",
 "A C C C A A b b c B b B a B b b B C B A b B C c B ",
 "A a B b A B c c c C C c b b C b B c A c c c A a c ",
 "a a C B B a c c c C a A C a b A C C C a c A A C A ",
 "A a a c c C B b b c a B B c B C b A a a A a B A a ",
 "C B C b a A B C B B B b b B C c B b a c C c C C C ",
 "C a b B B b b A B C b b A C c b A B A B a a B c c ",
 "C A B A B C a B C C c C C b C A B c c a A a C C c ",
 "C b C B a C c a C b a C a c a C c A b A A C b C B ",
 "a c A a B C C b B A b b B A a A C b C C a C c c c ",
 "b B b C b C b A a a B C C C A B b A C B B a c b C ",
 "C a c C B A B B B b C B c a C c C b C A A c b a B ",
 "a b c c B A B C A b c b A c a C A C C A A c b A a ",
 "B c B c b c b C a C C b c b C B C C B c B a A C A ",
 "c A A a a b A C C C B A B A a b B A B C a A b c b ",
 "A A b b C A A A c c a b A C c A A A C c A c B A c ",
 "A a c c c B a C b a c B a A C c c C c C c C C a C ",
 "A c C c b b a a a b A b c b B C c A B B a a b C C ",
 "a c A a C B A a b B a A B A A B c c A a c b b c a "}
"a...b...c...b...a"
Returns: { "10 0 [A B C b a]",  "13 0 [A b c b a]",  "22 28 [a b C b a]",  "43 16 [A b c b A]",  "10 0 [A B C b a A]" }

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

Coding Area

Language: C++17 · define a public class bloggoSequenceSearch with a public method vector<string> findPassages(vector<string> documents, string query) · 53 test cases · 2 s / 256 MB per case