Considere as cadeias X e Y com os respectivos caracteres Xi...

Considere as cadeias X e Y com os respectivos caracteres X_i e Y_j , onde deseja-se verificar se Y é subcadeia de X e, em caso positivo, deve-se localizar Y em X. Dados:

➢ 1< i < n

➢ 1 < j < m

➢ m < n

➢ I= variável que indica o número de caracteres na cadeia X

➢ teste = uma variável lógica

Dado o seguinte algoritmo, conhecido em processamento de cadeias:

para I := 0, ... , n-m faça

i:=1

teste := V

enquanto < m e teste faça

se x[ I + i ] = y [i] então

i:=i+1

senão teste := F

se teste então

" casamento na posição I + 1 "

Pare

" não há casamento "

Pelos passos apresentados, como é conhecido o algoritmo?