TwiceString
SRM 518 · 2011-05-25 · by omeometo
SRM 518 · 2011-05-25 · by omeometo · String Manipulation
Problem Statement
Problem Statement
You are given a
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').
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