Cyclic word equality problem: given two strings A and B with n letters. How many letter comparisons are necessary to decide, if A and B are equal under cyclic rotation? This means: does there exist a shift s, such that for all 0<=k