square_free_word.py

from __future__ import division, print_function
from string import maketrans
import re


def thue_morse(n):
    comp = maketrans('01', '10')
    s = '0'
    for _ in range(n):
        s += s.translate(comp)
    return map(int, s)


def first_diff(s):
    return [s[i] - s[i-1] for i in range(1, len(s))]


def to_abc(a):
    return ''.join({-1: 'a', 0: 'b', 1: 'c'}[i] for i in a)


def john_leech(n):
    w = 'a'
    for _ in range(n):
        x = ''
        for c in w:
            if c == 'a':
                x += 'abcbacbcabcba'
            elif c == 'b':
                x += 'bcacbacabcacb'
            else:
                x += 'cabacbabcabac'
        w = x
    return w


def is_square_free(w):
    n = len(w)
    for j in range(1, n // 2 + 1):
        for i in range(n):
            if i + j > n - j:
                break
            # print(w[i:i+j], w[i+j:i+j+j])
            if w[i:i + j] == w[i + j:i + j + j]:
                # print(w[i:i+j], w[i+j:i+j+j])
                return False
    return True


def is_square_free2(w):
    return re.search('(.+)\\1', w) is None