Loop Invariant Initialisation Confusion

Question

Considérez l'algorithme Lastmatch ci-dessous, qui renvoie le décalage (décalage) de la dernière occurrence du motif P dans le texte T, ou -1 si P ne se produit pas dans T:

LastMatch(T,P)
 for(s = T.length - P.length downto 0)
   j = 1
   while(j =< P.length and P[j] == T[s + j])
     j++
   if(j == P.length + 1)
     return s
 return -1

On m'a donné une boucle invariante pour la boucle while:

$ forall k (1 leq k

L'initialisation de cet invariant me confond. Avant d'entrer dans la boucle while, $ j = 1 $. Alors nous demandons qu'il y a un 1 $ leq k <1 $ tel que $ P [k] == t [s + k] $?

Je ne trouve pas un $ k $ Ce qui satisfait cette inégalité, donc je ne comprends pas ce que cela dit. Alors pourquoi l'invariant est-il satisfait avant d'entrer dans la boucle? Est-ce parce que lorsque je ne trouve pas un $ k $ cela implique que $ P [k] $ et $ T [s + k] $ sont les deux égaux à l'ensemble vide?