Algoritmo banale ingenuo per risolvere il problema dello string

Algoritmo banale ingenuo per risolvere il problema dello string-matching esatto, qui presentato:
1.
2.
3.
4.
5.
6.
NAIVE (P, m, T, n)
for s
to n-m do
i
while (i
m and P[i] J[S+i]) do
i
i+1
if (i
m) then
output (s)
Il ciclo delle righe 3-4 ha complessità ( ), mentre il ciclo delle righe 1-6 viene eseguito
volte, per
) )
(
)
( ) (l’ultima vale perché
una complessità dell’algoritmo di ((
).
{
} alfabeto, ove
| |, e supponiamo che la probabilità del generico carattere
Sia
apparire alla posizione di un testo qualsiasi sia uniforme, ovvero:
{ []
{
}
di
}
Parimenti, si calcola, quindi la probabilità che due caratteri siano diversi come la probabilità dell’evento
opposto all’evento di essere uguali come:
{
}
{
}
Poniamo
evento “effettuo esattamente confronti prima di rilevare mismatch (o di uscire dall’array)”
Calcoliamo ora i valori di { } supponendo che il pattern non sia la stringa vuota:
{
}
{
}
{ [ ]
[ ]}
{
}
{ [ ]
[ ]
[ ]
[ ]}
{
}
{ [ ]
[ ]
[ ]
[ ]
{
}
, giacché è impossibile che non facciamo nemmeno un confronto
{ }
{(⋀ [ ]
}
}
{
[ ])
{
{
{
{ [ ]
[ ]
}
[]
}
[ ]}
{ [ ]
{ [ ]
[ ]}
[ ]}
{
{ [ ]
}
[ ]}
{
}
{ [ ]
[ ]}
( )
[ ]}
{
[ ]}
}
(∏
{ []
[ ]})
{ []
[ ]}
( )
{“faccio mismatch sull’ultimo simbolo” “tutti simboli uguali”}
(essendo due eventi indipendenti, posso sommare le rispettive probabilità)
Sia =numero di confronti da fare e
{
}
Ma
∑
l’evento che indica che bisogna fare almeno confronti. Allora:
{ }
è anche l’evento corrispondente ad “aver trovato
[ ]
∑
{ }
∑
(
(
{
)
)
}
∑
(
caratteri uguali”, quindi:
∑( )
)
(
∑( )
)
( )
( )