Скачиваний:
34
Добавлен:
02.05.2014
Размер:
1.22 Кб
Скачать
#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();
}