Добавил:
Studfiles2
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Шпоры по МПиПА / Строки / Алгоритм Кнута Морриса и Пратта / C / Исходник / KMP
.cpp#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();
}