CCC '20 J4 - Cyclic Shifts

View as PDF

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
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 ABCCDEABAA.

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.

• commented on Nov. 23, 2023, 6:41 p.m.

this felt a bit too simple for a j4, i feel like i lucked out here or something with choice of language. my submission was like a test attempt that i thought i was gonna have to optimize the hell out of but it just worked

• commented on Jan. 29, 2024, 5:49 p.m.

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on Feb. 11, 2024, 11:45 p.m.

🤓☝

• commented on Feb. 17, 2023, 8:07 a.m.

Can my submission be deleted?

• commented on Dec. 30, 2022, 5:36 a.m.

My program seems to work on every test case I give it, but IndexErrors whenever i actually submit it on the first case that's not a test case. Could someone explain what's wrong? Thanks

• commented on Jan. 2, 2023, 12:41 a.m. edited

Your algorithm seems to be unnecessarily complicated for this problem. Try a solution that modifies the original string and checks operations on that.

• commented on Dec. 27, 2022, 1:05 a.m.

when you TLE the very last test case :'(

• commented on May 26, 2022, 11:41 p.m.

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on May 29, 2022, 12:47 a.m.

says the one who failed 15 times after you solved it

• commented on Feb. 21, 2022, 9:20 a.m.

When you see such an efficient and concise solution like the one by austin_1 (PY3). Facepalm...

• commented on Feb. 13, 2022, 7:18 p.m.

is someone able to check my program, i do not understand why it is wrong Thanks!

• commented on Feb. 13, 2022, 7:44 p.m.

• commented on March 8, 2021, 4:44 a.m.

What are the contraints for the length of ?

• commented on March 8, 2021, 4:58 a.m.

Each line will contain at most 1000 characters.

• commented on March 8, 2021, 5:00 a.m.

Thank you for clarifying.

• commented on March 8, 2021, 5:00 a.m.

Happy to help!

• commented on March 26, 2020, 3:42 a.m.

Can anyone explain what's wrong with my program?

• commented on March 26, 2020, 3:43 p.m.

Hashing isn't required, and your algorithm checks if a permutation of S occurs in T, and not all permutations are cyclic shifts.