CCC 2020 J4:Cyclic Shifts

https://www.cemc.uwaterloo.ca/contests/computing/2020/ccc/juniorEF.pdf

Solution:

Two strings are T and S, T length > S length.

1. Check if ith to ith+Slength has the same chars as S. Maintenance a window, slide in T, It is from i to i+len(S), next will be i+1 to i+1+len(S). using sum to do it. sum = sum(window) - ord(T[i]) + ord(T[i+1+len(S))

2. if ith to ith+len(S) substring is in S+S, return true, it is S cyclic shifts, otherwise not

3. if it is S cyclic shifts, print "yes"

4. Iterative whole T, if not find one S cyclic shifts, print "no"

Time complexity: O(len(T))

T = input()
S = input()
slen = len(S)
tlen = len(T)
charnum = 0
DS = S + S
for i in range(slen):
    charnum += ord(T[i]) - ord(S[i])

def iscycle(mystring):
    if mystring in DS:
        return True
    return False


if charnum == 0 and iscycle(T[0:slen]):
    print("yes")
else:
    findone = False
    for i in range(slen, tlen):
        charnum -= ord(T[i-slen])
        charnum += ord(T[i])
        if charnum == 0 and iscycle(T[i-slen+1:i+1]):
            findone = True
            print("yes")
            break
    if not findone:
        print("no")