Скачиваний:
32
Добавлен:
02.05.2014
Размер:
1.12 Кб
Скачать
#include "iostream.h"
#include "stdio.h"
#include "string.h"

int KMPSearch(char str[], char substr[] ){
	int  i, j, k, M, N;
	int  *d;
	N = strlen(str);
	M = strlen(substr);
	if ( N == 0 ){ 
		printf("Wrong string: "); 
		return -1;
	}
    if ( M == 0 ){
		printf("Wrong substring: "); 
		return -1; 
	}

	j = 0;
    k = -1;
	d = new int[1000];
    d[0] = -1;
    while ( j< M - 1 ){
		while ( k >= 0 && substr[j] != substr[k] ){
			k = d[k];
		}
		j++;
		k++;
		if ( substr[j] == substr[k] ){
			d[j] = d[k];
		} else {
			d[j] = k;
		}
	}

     i = 0;
     j = 0;
     while ( j < M && i < N ){
		 while ( j >= 0 && str[i] != substr[j] ) { j = d[j]; }
		 i++;
		 j++;
     }

     if ( j == M ) { return i - M; }
     else { return -1; }
}

void main(){
int nMax = 1000;
char *substr,*str;
str = new char[nMax];
substr = new char[nMax];
	 cout << "Knuth Morris Pratt Algoritm.\nString: ";
	 cin >> str;
	 cout << "Substring: ";
	 cin >> substr;
	 cout << "Result: " << KMPSearch( str, substr ) << "\nPress any key to continue..." << endl;
     getchar();
}