## CCC '20 J4 - Cyclic Shifts (Hard)

View as PDF

Points: 12 (partial)
Time limit: 0.4s
Java 0.6s
Python 0.7s
Memory limit: 512M

Author:
Problem type

This is an extension of ccc20j4. In this version, the constraints are higher.

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.

Each line will contain at most characters.

Tip: the intended solution runs well within the time limit without constant optimization.

#### 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.

• commented on Jan. 30, 2022, 1:44 p.m. edit 4

Can this be solved using Python within the time limits? No accepted solutions for python or pypy exist.

 I see that there is an explicit time limit for python which suggests it ought to be solvable.

I'm stuck on 90%. Getting TLE on 2nd problem in part 3.

• commented on Jan. 29, 2022, 12:17 p.m.

A mystery to solve: why can't I exit() in python? I get NameError if I exit() rather than use logic to control program flow.

• commented on Jan. 29, 2022, 12:55 p.m.
• commented on Jan. 30, 2022, 1:45 p.m.

That would explain it :)

• commented on Jan. 30, 2022, 3:04 p.m.

you can still use sys.exit(0) however