El algoritmo de búsqueda de cadenas de Boyer-Moore es un algoritmo de propósito general para encontrar una subcadena en una cadena.
Intentemos encontrar la ocurrencia de una subcadena en una cadena.
Nuestro código fuente será:
Text: somestring
Y el patrón que estaremos buscando
Pattern: string
Pongamos los índices en nuestro texto para ver en qué índice se encuentra cada letra.
0 1 2 3 4 5 6 7 8 9
s o m e s t r i n g
Escribamos un método que determine si el patrón está en una cadena. El método devolverá el índice desde donde el patrón entra en la cadena.
int find (string text, string pattern){}
En nuestro ejemplo, debería devolver 4.
0 1 2 3 4 5 6 7 8 9
text: s o m e s t r i n g
pattern: s t r i n g
Si no se encuentra una respuesta, devolveremos -1
int find (string text, string pattern) {
int t = 0; .
int last = pattern.length — 1;
Creemos un bucle para recorrer el texto.
while (t < text.length — last)
? , . .
:
last = 5 ( string 5)
10 (somestring)
text.length — last = 10–5 = 5;
0 1 2 3 4 5 6 7 8 9
text: s o m e s t r i n g
pattern: s t r i n g
, 5 , 4 , ,
0 1 2 3 4 5 6 7 8 9
text: s o m e X t r i n g
^
pattern: s t r i n g
, .
:
int find (string text, string pattern) {
int t = 0;
int last = pattern.length — 1;
while (t < text.length — last){
}
}
int p = 0, .
while( p <= last && text[ t + p ] == pattern[p] ){
}
p <= last —
text[ t + p ] = pattern[p] — .
, text[ t + p ] = pattern[p]
4
0 1 2 3 4 5 6 7 8 9
text: s o m e s t r i n g
^
pattern: s t r i n g
t = 4, p = 0; text[ t + p ] = text[ 4 + 0 ] = s, pattern[0] = s, .
:
int find (string text, string pattern) {
int t = 0;
int last = pattern.length — 1;
while (t < text.length — last) {
int p = 0;
while( p <= last && text[ t + p ] = pattren[p] ){
, p .
p ++;
}
p == pattern.length
.
if (p == pattern.length){
return t;
}
.
t ++;
}
}
:
int find (string text, string pattern) {
int t = 0;
int last = pattern.length — 1;
while (t < text.length — last) {
int p = 0;
while( p <= last && text[ t + p ] == pattern[p] ) {
p ++;
}
if (p == pattern.length) {
return t;
}
t ++;
}
return — 1;
}
? ?
, .
text: some*string , ?
?
,
text: somestring
^
pattern: string
^
. , ?
, .
text: somestring
pattern: string
.
text: somestring
^
pattern: string
^
pattern[i] = ‘g’, text[i] = ’t’,
pattern.length — ’t’ .
’t’ = 1, 5–1 = 4, 4 .
text: somestring
^
pattern: >>>>string
^
.
, .
, . * .
:
s 0
t 1
r 2
i 3
n 4
g 5
* -1
, , , :
pattern:
4
2 — ,
-1
-1
5
, , .
:
int[] createOffsetTable(string pattern) {
int[] offset = new int[128]; //
//
for (int i = 0; i < prefix.length; i++){
offset[i] = -1; //
}
for (int i = 0; i < pattern.length; i++){
offset[pattern[i]] = i;
}
return offset;
}
, :
int find (string text, string pattern) {
int[] offset = createOffsetTable(pattern);
int t = 0;
int last = pattern.length — 1;
while (t < text.length — last){
int p = last; //
// ,
//
while( p >= 0 && text[ t + p ] == pattern[p] ){
p — ;
}
if (p == -1){
return t;
}
t += last — offset[ text[ t + last ] ];
}
return — 1;
}
t + last ? . , , + .
:
:
= 4
= 2
= 5
1:
0 1 2 3 4 5 6 7 8 9 10
text:
pattern:
last = 7;
t += last — offset[text[t + last]]
t += last — offset[text[0 + 7]]
t += last — offset[‘’]
t += 7–5 = 2;
t = 2;
2:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
text:
pattern: > >
t = 2;
t += last — offset[text[t + last]]
t += last — offset[text[2 + 7]]
t += last — offset[‘’]
t += 7–5 = 2;
t = 4;
3:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
text:
pattern: > > > >
t = 4;
t += last — offset[text[t + last]]
t += last — offset[text[4 + 7]]
t += last — offset[‘’]
t += 7–5 = 2;
t = 6;
4:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
text:
pattern: > > > > > >
t = 6;
t += last — offset[text[t + last]]
t += last — offset[text[6 + 7]]
t += last — offset[‘’]
t += 7–5 = 2;
t = 8;
5:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
text:
pattern: > > > > > > > >
.
- .
. ?
abcdadcd
. .
d, ? . 2 d 2 4. 2 .
4
-----—
| 2
| ---
| | |
abcdadcd
^
cd. d 2.
2
abcdadcd
cd,
-- 4 .
= 4.
842
abcdadcd
dcd. dcd .
--- = 8
8, .
.
* *, c , 1.
1
*
—
41
*
-—
441
*
--—
4441
*
---—
4441
*
----
Para Okol también escribimos el 4 . Porque nuestro prefijo es el mismo que el sufijo.
Intentemos escribir el código para esto
createSuffix(string pattern){
int[] suffix = new int[pattern.length + 1]; // +1
for(int i = 0; i < pattern.length; i ++){
suffix[i] = pattern.length; // ,
// .
}
suffix[pattern.length] = 1; // 1
// , .
for (int i = pattern.length — 1; i >= 0; i — ) {
for (int at = i; at < pattern.lenth; at ++){
string s = pattern.substring(at); //
Por ejemplo, ¿con qué es la campana para comparar?
--—
--—
---
---
---
, , ,
for (int j = at — 1; j >= 0; j — ) {
string p = pattern.substring(j, s.length); //
//
if (p.equals(s)) {
suffix[j] = at — i;
break;
}
}
}
}
return suffix;}
Hay un algoritmo más óptimo, pero más individualmente.
¿Qué código tenemos en este momento?
int[] createSuffix (string pattern) {
int[] suffix = new int[pattern.length + 1];
for (int i = 0; i < pattern.length; i ++){
suffix[i] = pattern.length;
}
suffix[pattern.length] = 1;
for (int i = pattern.length — 1; i >=0; i — ){
for(int at = i; i < pattern.length; i ++){
string s = pattern.substring(at);
for (int j = at — 1; j >= 0; j — ){
string p = pattern.substring(j, s.length);
if (p == s) {
suffix[i] = at — 1;
at = pattern.length;
break;
}
}
}
}
return suffix;
}
int find(string text, string pattern) {
int[] offset = createOffset(pattern);
int[] suffix = createSuffix(pattern);
int t = 0;
int last = pattern.length — 1;
while (t < text.length — last) {
int p = last;
while (p >= 0 && text[t + p] == pattern[p]) {
p — ;
}
if (p == -1) {
return t;
}
t += Math.max (p — offset[text[t + p]], suffix[p + 1]);
}
return -1;
}
p - prefijo [texto [t + p]] - el último carácter que se encontró y ajustar el desplazamiento de nuestra plantilla para él
sufijo [p + 1] : el valor del sufijo para el último elemento que se comparó.
Y nos movemos al valor máximo para poder movernos lo más rápido posible.
Con esto concluye el análisis del algoritmo de Boyer-Moore. ¡Gracias por la atención! =)