Connection Status:
Competition Arena > TwiceString

TwiceString

SRM 518 · 2011-05-25 · by omeometo

SRM 518 · 2011-05-25 · by omeometo · String Manipulation
Class Name: TwiceString
Return Type: String
Method Name: getShortest
Arg Types: (string)
Problem Statement

Problem Statement

You are given a String s. Return the shortest string which contains s as a contiguous substring twice.

Note that two occurrences of s may overlap. For example, "ababa" contains "aba" twice.

Notes

  • The shortest string which contains s as a contiguous substring twice is always unique.

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • Each character in s will be a lowercase letter ('a'-'z').

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
"aba"
Returns: "ababa"

This is the example shown in the problem statement.

1)
"xxxxx"
Returns: "xxxxxx"
2)
"topcoder"
Returns: "topcodertopcoder"
3)
"abracadabra"
Returns: "abracadabracadabra"
4)
"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
Returns: "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
7)
"mstrrrwtsgdcplbixiomtegvevtlzwpkdsqfvg"
Returns: "mstrrrwtsgdcplbixiomtegvevtlzwpkdsqfvgmstrrrwtsgdcplbixiomtegvevtlzwpkdsqfvg"

Tomorrow is the SRM, so let me add 100 random test cases. (No, it wasn't, sorry for flooding test cases for no reason, feel free to replace).

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

Coding Area

Language: C++17 · define a public class TwiceString with a public method string getShortest(string s) · 128 test cases · 2 s / 256 MB per case

Submitting as anonymous