Швидкий пошук (Класифікація Thierry Lecroq )

Зрушення поганого символу, який використовується в алгоритмі Боуер - Мура, не дуже ефективний для маленького алфавіту, але, коли розмір алфавіту велику у порівнянні з довжиною зразка, як це часто має місце з

таблицею ASCII і при звичайному пошуку в текстовому редакторі, він стає надзвичайно корисний. Використання в алгоритмі тільки його одного може бути досить ефективним.

Після спроби поєднання x і y [i, i + m-1], довжина зсуву - не менше 1. Таким чином, символ y [i + m] обов'язково буде залучений в наступну спробу, а значить, може бути використаний в поточній спробі для зрушення поганого символу. Модифікуємо функцію поганого символу, щоб прийняти до уваги останній символ х:

bc [a] = min {j | 0 j m і x [m - 1 - j] = a}, якщо a зустрічається в x,

bc [a] = m в протилежному випадку.

Порівняння тексту і зразка можуть проводитися у будь-якому порядку.

Турбо БМ (Класифікація Thierry Lecroq ).

Турбо - БМ є також є поліпшенням алгоритму Боуер - Мура. Ми будемо запам'ятовувати сегмент тексту, який зійшовся з суфіксом зразка під час минулої спроби (і тільки, якщо стався зсув хорошого суфікса).

Це дасть нам дві переваги:

1. Можливість перескочити через цей сегмент

2. Можливість застосування «турбо - зсуву»

«Турбо - зрушення» може відбутися, якщо ми виявимо, що суфікс зразка, який збігається з текстом, коротше, ніж той, який був запам'ятати раніше.

Нехай u - запомненний сегмент, а v - cуффікс, який співпав під час поточної спроби, такий що uzv - суфікс x. Тоді av - суфікс x, два символи а і b зустрічаються на відстані p в тексті, і суфікс x довжини | uzv | має період довжини p, а значить не може перекрити обидва появи символів а і b у тексті. Найменший можливий зсув має довжину | u | - | v | (його ми і називаємо «турбо - зрушенням»).

Пошук підрядка в рядку за допомогою хеш-функції

Пошук підрядка в рядку - часто виникає на практиці завдання. Пошук підрядка в рядку звичайної підстановкою до кожної позиції рядка всій підрядка - метод неефективний і взагалі сумний. Я розгляну метод пошуку за допомогою хеш-функції - досить простий і швидкий.

Кожен символ має свій унікальний код від 0 до 255. Суть методу полягає в тому, щоб для підрядка підрахувати деяку хеш-функцію (наприклад суму кодів всіх символів у рядку), потім порахувати ту ж саму хеш-функцію для частини рядка, що дорівнює по довжині підрядку, і, в разі збігу хеш-функції, повністю порівняти його. Прискорення роботи алгоритму пов'язано з тим, що ми кожного разу не перераховуємо щоразу хеш-функцію, а тільки забираємо значення функції від самого "старого" символу і додаємо значення функції від наступного символу.

 

Індивідуальне завдання

Програмно реалізувати «Не такий вже й наївний» алгоритм пошуку підрядка в рядку.

 

#include<iostream>

#include<string.h>

using namespace std;

int NSN( char *x, char *y, int n, int m )

{

int i, k, l;

char secondch, firstch, *thirdch;

if ( x[ 0 ] == x[ 1 ] )

{

k = 2;

l = 1;

}

else

{

k = 1;

l = 2;

}

/* Searching */

i = 0;

firstch = x[ 0 ];

secondch = x[ 1 ];

thirdch = &x[ 2 ];

while ( i <= n - m )

{

cout<<"i="<< i<<endl ;

if ( y[ i + 1 ] != secondch ) i+=k;

else {

cout<<"Maybe in i="<< i<<endl ;

//cout<<memcmp(&y[ i + 2 ], thirdch, m - 2 );

if ( memcmp(&y[ i + 2 ], thirdch, m - 2 ) == 0

&& y[ i ] == firstch )

{

cout<<"Exacly in i="<<i<<endl;

return i;

}

}

}

return -1;

}

int main()

{

char str[300];

char sub[300];

string s,s_find;

cin.getline(str,256);

cin.getline(sub,256);

int l,l_find;

l=strlen(str);

l_find=strlen(sub);

cout<<"l="<<l<<endl;

cout<<"l_find="<<l_find<<endl;

int result = NSN(sub,str,l,l_find);

if(result==-1)cout<<"Nema takoji pidstrichki\n";

else cout<<"Pidstrichka pochinajetsa z #="<<result+1<<"\n";

system("pause");

return 0;

}

 

Висновок:Ознайомилася з алгоритмами пошуку підрядків в рядку. Програмно реалізувала один із них.