Cyclic Shifts

Interview

Time limit2sMemory limit512 MB

Summary

Given a text T and a string S, decide whether T contains any cyclic shift of S as a contiguous substring.

Level: Easy3 of 10
Topics: String, String matching, Sliding window, Brute force
Solved: No attempts yet

Problem

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, T, and a string, S, determine if T contains a cyclic shift of S.

Input

The input consists of exactly two lines containing only uppercase letters. The first line is the text T, and the second line is the string S. Each line contains at most 1000 characters.

Output

Output yes if the text, T, contains a cyclic shift of the string, S. Otherwise, output no.

Examples2

Example 1
Input
```
ABCCDEABAA
ABCDE
```
Expected output
```
yes
```
Example 2
Input
```
ABCDDEBCAB
ABA
```
Expected output
```
no
```