# Efficiently generate prefixes of the OEIS sequence https://oeis.org/A356677
# using the Main-Lorentz algorithm testing whether a word is square-free.

# See Main, M.G., Lorentz, R.J.: Linear time recognition of squarefree strings.
# In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words. NATO
# ASI Series, vol. F 12, pp. 271–278. Springer, Heidelberg (1985).

# ml_square_suffix is a modification to the Main-Lorentz algorithm that only
# checks for square suffixes.

"""
Returns a list of the starting positions of the occurrences of s in w with
starting position start <= i <= end.
Requires that w contains no squares xx with len(x) < len(s).

>>> sub_search([1,2], [3,1,2,3,2,3,4,1,2,4,2,1,2], 0, 12)
[1, 7, 11]
>>> sub_search([1,2], [3,1,2,3,2,3,4,1,2,4,2,1,2], 1, 11)
[1, 7, 11]
>>> sub_search([1,2], [3,1,2,3,2,3,4,1,2,4,2,1,2], 2, 10)
[7]
"""
def sub_search(s,w,start,end):
    # do not try to search past the end of the word
    end = min(end, len(w)-1)
    occurrences = []
    L = len(s)
    starting_pos = start
    pos = start
    i_pos = 0
    while starting_pos <= end:
        if w[pos] == s[i_pos]:
            i_pos += 1
            pos += 1
            if i_pos >= L:
                # found an occurrence of s
                occurrences.append(starting_pos)
                starting_pos = pos
                i_pos = 0
        else:
            # found a mismatch
            pos += 1
            starting_pos = pos
            i_pos = 0
    return occurrences

def longest_common_prefix(w1,w2):
    L = min(len(w1),len(w2))
    pref_len = 0
    while pref_len < L and w1[pref_len] == w2[pref_len]:
        pref_len += 1
    return pref_len

def longest_common_suffix(w1,w2):
    L = min(len(w1),len(w2))
    suff_len = 0
    while suff_len < L and w1[-1-suff_len] == w2[-1-suff_len]:
        suff_len += 1
    return suff_len

"""
Returns true iff w has a square suffix.
Requires that w[:-1] is square-free. Cannot be used to compute L(w) when w
contains a square.
Modification of the Main-Lorentz algorithm.

>>> ml_square_suffix([1,2])
False
>>> ml_square_suffix([1,1])
True
>>> ml_square_suffix([1,0,3,0,1,0,2,0,1,0])
False
>>> ml_square_suffix([1,0,2,0,1,0,2,0,1,0])
True
>>> ml_square_suffix([1,0,2,0,1,0,2,0,3,0])
False
"""
def ml_square_suffix(w):
    n = len(w)
    l = 1
    while 2*l-1 <= n/2:
        # find occurrences of w[-l:] in the first half of the potential square
        occurrences = sub_search(w[-l:], w, max(0,n-5*l+2), max(0,n-3*l+1))
        for j in occurrences:
            if w[j+l:] == w[2*(j+l-n):j+l]:
                return True
        # next power of 2
        l = 2*l
    return False

"""
Returns a list of the first n letters of L(word).
"""
def build_square_free(word, n):
    new_word = word[:]
    while len(new_word) < n:
        next_letter = 0
        # find the least letter that does not introduce a square
        while ml_square_suffix(new_word+[next_letter]):
            next_letter += 1
        new_word += [next_letter]
    return new_word

"""
Returns a list of the first n terms of A356677.
"""
def A356677_list(n):
    return build_square_free([1], n)