def recherche(M,T):
    i = 0
    while i < len(T) :
        j = 0
        while (i+j < len(T)) and (j < len(M)) and (T[i+j] == M[j]):
            j += 1
            if j == len(M):
                return i
        i += 1
    return -1

##
def fonctionannexe(M):
    F=[0]
    i=1
    j=0
    while i < len(M) : # m n'est pas défini: m=len(M)
        if M[i]==M[j] : # un seul =
            F.append(j+1)
            i=i+1
            j=j+1
        else: #oubli du :
            if j>0 :
                j=F[j-1]
            else:
                F.append(0)
                i=i+1
    return F

L=fonctionannexe('CATCGCATCG')
print(L)

def KMP(M,T):
    F=fonctionannexe(M)
    print(F)
    i=0
    j=0
    while i < len(T) :
        if T[i]==M[j]:
            if j==len(M)-1:   
                return(i-j)
            else:
                i=i+1
                j=j+1
        else:
            if j > 0:
                j=F[j-1]
            else:
                i=i+1
    return -1
    
print(KMP('CGC','CATCGCATCG'))

## tri
L=['C','A','T','G','CA','AT','TC','CG','CAT','ATC','TCG','CATC','ATCG','CATCG'] 
def tri_selection(T):
    for i in range(len(T)-1):
        for j in range (i+1, len(T)):
            if T[i]>T[j] : 
                T[i],T[j]=T[j],T[i]
    return T

Lalpha=tri_selection(L)
print(Lalpha)

def recherchedichotomique(a,L):
    c = 0
    l = len(L)
    m = (c+l)//2
    while c < l :
        if L[m] == a :
            return m
        elif L[m] > a :
            l = m-1
        else :
            c = m+1
        m = (c+l)//2
    return m

print (recherchedichotomique('ATCG',Lalpha))

def dico(L,a):
    n=len(L)
    m=0
    while m!=a:
        m=L[n//2]
        if m<a:n=(n+n//2)//2
        if m>a:n=n//4
    return n//2
print(dico([i for i in range(100)],99))