Connection Status:
Competition Arena > TemplateMatching

TemplateMatching

SRM 417 · 2008-09-10 · by Pawa

SRM 417 · 2008-09-10 · by Pawa · Brute Force, String Parsing
Class Name: TemplateMatching
Return Type: String
Method Name: bestMatch
Arg Types: (string, string, string)
Problem Statement

Problem Statement

In this problem you will be given a String text and you will need to find the substring of the text that matches a given template in the best way. The template will be represented by two Strings: prefix and suffix. Consider a string S. The prefix match score of S with respect to a given template is the maximal n >= 0 such that the first n characters of S are equal to the last n characters of prefix and occur in the same exact order. Analogously, the suffix match score of S is the maximal m >= 0 such that the last m characters of S are equal to the first m characters of suffix and occur in the same exact order.


For example, if S = "something", prefix = "awesome", and suffix = "ingenious", than the prefix score of S is 4 (the matched characters are "some") and the suffix score is 3 (the matched characters are "ing").


The match score of a string S with respect to a given template is the sum of its prefix and suffix match scores. Find the non-empty substring of text with the maximal match score according to the template (prefix, suffix). In case of a tie, return the substring with the maximal prefix score. If there are still several candidates, return one that comes first lexicographically.

Notes

  • String A comes before string B lexicographically if A is a proper prefix of B, or if A has a smaller character at the first position where the strings differ. When comparing the characters, refer to the following list of characters in ascending order: ' ', 'a', 'b', ..., 'z'.

Constraints

  • text will contain between 1 and 50 characters, inclusive.
  • prefix will contain between 1 and 50 characters, inclusive.
  • suffix will contain between 1 and 50 characters, inclusive.
  • text, prefix and suffix will contain only lowercase letters ('a'-'z') and spaces (' ').
Examples
0)
"something"
"awesome"
"ingenious"
Returns: "something"

The example from the problem statement.

1)
"havka"
"eto"
"papstvo"
Returns: "a"

The return value must be non-empty string, so the correct answer is "a".

2)
"a"
"b"
"c"
Returns: "a"

The return value must be non empty string, so the correct answer is "a".

3)
"abracadabra"
"habrahabr"
"bracket"
Returns: "abrac"
4)
"mississippi"
"promise"
"piccolo"
Returns: "ippi"

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

Coding Area

Language: C++17 · define a public class TemplateMatching with a public method string bestMatch(string text, string prefix, string suffix) · 111 test cases · 2 s / 256 MB per case

Submitting as anonymous