TemplateMatching | Topcoder Archive

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.

Definition

Class:: TemplateMatching
Method:: bestMatch
Parameters:: String, String, String
Returns:: String
Method signature:: String bestMatch(String text, String prefix, String suffix)
(be sure your method is public)

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

"something"

"awesome"

"ingenious"

Returns: "something"

The example from the problem statement.

```
"havka"
```
```
"eto"
```
```
"papstvo"
```
```
Returns: "a"
```
The return value must be non-empty string, so the correct answer is "a".

"abracadabra"

"habrahabr"

"bracket"

Returns: "abrac"

"mississippi"

"promise"

"piccolo"

Returns: "ippi"

```
"a a a a a a"
```
```
"a a"
```
```
"a"
```
```
Returns: "a a"
```
```
"ab"
```
```
"b"
```
```
"a"
```
```
Returns: "b"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.