#Generating $q$-ary words avoiding a given factor f

#initialization
reset()
n=6 # length of the sequences, changeable
q=3 # -arity, changeable
factor=[0,1,1,2] #forbidden factor, changeable
#prepend it with a 0
#ex: if  f=112, then factor=[0,1,1,2]
size_f=len(factor)-1
border=[-1]
for i in [1..size_f]:
    border.append(0)
M=matrix(size_f,q,0)
b=[]
for i in range(n+1):
    b.append(0)
L=[]

def type():
    t=Sequence(b[1:n+1])
    L.append(t)
    print L.index(t)+1,t

def make_border():
    i=0
    for j in [1..size_f-1]:
        border[j]=i
        while i>=0 and factor[j+1]!=factor[i+1]:
            i=border[i]
        i=i+1
    border[size_f]=i

def make_array():
    for j in [0..q-1]:
        for i in [0..size_f-1]:
            if factor[i+1]==j:
                M[i,j]=i+1
            elif i>0:
                M[i,j]=M[border[i],j]
            else:
                M[i,j]=0

def GenAvoid(j,drc,i):
    if(j==n+1):
        type()
    else:
        if i==size_f-1:
            u=factor[size_f]
        else:
            u=-1
        if drc==0:
            for k in [0..q-1]:
                if k!=u:
                    b[j]=k
                    m=0
                    if q%2==1 and k!=0:
                        m=1
                    GenAvoid(j+1,(drc+k+m)%2, M[i,k])
        else:
            for k in reversed [0..q-1]:
                if k!=u:
                    b[j]=k
                    m=0
                    if q%2==1 and k!=0:
                        m=1
                    GenAvoid(j+1,(drc+k+m)%2, M[i,k])

#Main call
make_border()
make_array()
GenAvoid(1,0,0)