Добавил:
Studfiles2
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Шпоры по МПиПА / Строки / Алгоритм Бойера Мура / С / Исходник / BM
.cpp#include "string.h"
#include "iostream.h"
#include "stdio.h"
int BMSearch( char str[], char substr[] ){
int Pos, ssl, sl, i;
int BMT[256];
if ( strlen(str) == 0 ){
cout << "Wrong string ";
return -1;
}
if ( strlen(substr) == 0 ){
cout << "Wrong substring ";
return -1;
}
ssl = strlen(substr);
sl = strlen(str);
for ( i = 0; i < 256; i ++ ){
BMT[i] = ssl-1;
}
for ( i = ssl-1; i >=0; i-- ){
if ( BMT[(short)(substr[i])] == ssl-1 ) {
BMT[(short)(substr[i])] = ssl - i - 1;
}
}
Pos = ssl - 1;
while ( Pos < sl ){
if ( substr[ssl - 1] != str[Pos] ){
Pos = Pos + BMT[(short)(str[Pos])];
}
else {
for ( i = ssl - 2; i >= 0; i-- ){
if ( substr[i] != str[Pos - ssl + i + 1] ) {
Pos++;
break;
}
else {
if ( i == 0 ) {
return Pos - ssl + 1;
}
}
}
}
}
return -1;
}
void main(){
char *s,*p;
int nMax = 1000;
s = new char[nMax];
p = new char[nMax];
cout << "Boyer and Moore Algoritm.\nString: ";
cin >> s;
cout << "Substring: ";
cin >> p;
cout << "Result: " << BMSearch(s,p);
cout << "\nPress any key to continue... " << endl;
getchar();
}