#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2026

"""
def chaines_egales (chaine1 , chaine2 ):
    n = len( chaine1 )
    i = 0
    while i < n:
        if chaine1 [i] != chaine2 [i]:
            return False
        i += 1
    return True

def liste_occurences(texte,mot):
    L=[] # si aucune occurence n'est trouvé on renvoie la liste vide
    n=len(mot)
    for i in range(len(texte)-n+1):
        if chaines_egales(texte[i:i+n], mot):
            L.append(i)
    return L


def premiere_occurence(texte,mot):
    L=liste_occurences(texte,mot)
    if L==[]:
        return None
    else:
        return min(L)
    
    
    
def longueur_bord (ch ):
    n = len(ch)
    jmax = 0
    for j in range (1,n): #n car la chaine entiere ne peut pas être le bord
        if chaines_egales(ch [:j],ch [n-j:]):
            jmax = j
    return jmax

def longueurs_bords_prefixes(ch):
    R=[]#résultat
    for i in range(len(ch)):
        R.append(longueur_bord(ch[:i+1]))
    return R

print(longueurs_bords_prefixes("AATGCAAT"))



def kmp(texte , mot ):
    n = len( texte )
    p = len(mot)
    B = longueurs_bords_prefixes (mot)
    i = 0
    j = 0
    while i <= len(texte)-len(mot) :
        while j < len(mot) and mot [j] == texte [i+j]:
            j += 1
        if j == len(mot) :
            return i
        if j == 0 :
            i = i+1
        else:
            i = i+j-B[j-1]
            j = B[j -1]
    return None