top of page

CCC 2020 J4:Cyclic Shifts


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")


Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,

留言


bottom of page