Canadian Computing Competition: 2020 Stage 1, Junior #4
Thuc likes finding cyclic shifts of strings. A cyclic shift of a string is obtained by moving characters from the beginning of the string to the end of the string. We also consider a string to be a cyclic shift of itself. For example, the cyclic shifts of ABCDE
are:
ABCDE
, BCDEA
, CDEAB
, DEABC
, and EABCD
.Given some text, , and a string,
, determine if
contains a cyclic shift of
.
Input Specification
The input will consist of exactly two lines containing only uppercase letters. The first line will be the text , and the second line will be the string
. Each line will contain at most
characters.
For of the
available marks,
will be exactly
characters in length.
Output Specification
Output yes
if the text, , contains a cyclic shift of the string,
. Otherwise, output
no
.
Sample Input 1
ABCCDEABAA
ABCDE
Output for Sample Input 1
yes
Explanation of Output for Sample Input 1
CDEAB
is a cyclic shift of ABCDE
and is contained in the text ABC
CDEAB
AA
.
Sample Input 2
ABCDDEBCAB
ABA
Output for Sample Input 2
no
Explanation of Output for Sample Input 2
The cyclic shifts of ABA
are ABA
, BAA
, and AAB
. None of these shifts are contained in the text ABCDDEBCAB
.
Comments
When you see such an efficient and concise solution like the one by austin_1 (PY3). Facepalm...
is someone able to check my program, i do not understand why it is wrong Thanks!
You're failing sample test cases, please try those first before asking.
What are the contraints for the length of
?
Thank you for clarifying.
Happy to help!
Can anyone explain what's wrong with my program?
Hashing isn't required, and your algorithm checks if a permutation of S occurs in T, and not all permutations are cyclic shifts.