## 2.4.1 ALGORITMO INGENUO

El texto y el patrón están definidos sobre un mismo alfabeto Σ. El texto es un arreglo de n elementos:T[1..n]

El patrón es un arreglo de m elementos (m ≤n): P[1..m]

Ocurrencia del patrón con desplazamiento s: ( ∃s: 0 ≤ s ≤n-m:( ∀j:1 ≤j ≤m:T[s+j]=P[j])).

“w es prefijo de x” (w [ x) si x= w.y (yεΣ*). Si w [ x luego, │w│ ≤ │ x │

Ejemplo

ab [ abcac “w es sufijo de x” (w ] x) si x = y.w

Ejemplo

cab ] abcab La notación Pk es equivalente a P[1..k], representa a los k caracteres prefijos de P. Tk representa a los k caracteres prefijo de T.

Notación

x,y,z: cadenas/ x ] z y y ] z. Si |x|≤ |y|, luego x ] y. Si |x| ≥|y|, luego y ]x. Si |x|=|y| luego x=y.

Un algoritmo ingenuo

Encontrar todos los desplazamientos s en el rango 0 ≤ s ≤n-m / P ] Ts+m P ocurre sólo una vez en T, en el desplazamiento s = 2.

STRING-MATCHER (T:Texto; P:Patrón)

{n = long(T);

m= long(P);

for (s=0; s <= n-m; s++)

if ( P[1..m] == T[s+1..s+m])

cout << “Matching con desplazamiento”>>s;

}

##