Connection Status:
Competition Arena > Patterns

Patterns

SRM 124 · 2002-12-12 · by dgoodman

SRM 124 · 2002-12-12 · by dgoodman
Class Name: Patterns
Return Type: int
Method Name: firstMatch
Arg Types: (string, string)
Problem Statement

Problem Statement

A "repetition pattern" describes a set of strings, all of which have the same number of letters and the same pattern of repeated letters. For example, a string satisfies the repetition pattern ABBDA if it contains exactly five letters, 3 of which are distinct, with the 1st and 5th matching and the 2nd and 3rd matching. "effze", "abbda", "zqqaz" all satisfy this pattern while "aaaaa", "abbd", and "dbbda" all fail to satisfy it. Note that the repetition pattern CAAZC describes exactly the same set of strings as does ABBDA.

Create a class Patterns that contains the method firstMatch that takes a String s and a String pat, the pattern, as inputs and returns the 0-based index in s where the first matching substring starts. If no substring of s matches pat, return -1.

Constraints

  • s contains between 1 and 50 characters, inclusive.
  • Each character in s is a lowercase letter 'a'-'z'.
  • pat contains between 1 and 50 characters, inclusive.
  • Each character in pat is an uppercase letter 'A'-'Z'.
Examples
0)
"nowisthetree"
"ABCA"
Returns: 5

"thet" and "etre" both satisfy the pattern ABCA. "thet" is first, starting at index 5.

1)
"abcdefghijklmnop"
"ZYX"
Returns: 0

Every 3 letter substring of this string s satisfies the pattern ZYX. "abc" is first.

2)
"abcdefghijklmnop"
"QQ"
Returns: -1
3)
"cabbabbabbaqc"
"ABBAC"
Returns: 7
4)
"abba"
"ABBAC"
Returns: -1
9)
"cd"
"CDCD"
Returns: -1

No substring of "cd" can have enough letters to match CDCD.

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

Coding Area

Language: C++17 · define a public class Patterns with a public method int firstMatch(string s, string pat) · 24 test cases · 2 s / 256 MB per case

Submitting as anonymous