You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
77 lines
2.3 KiB
C
77 lines
2.3 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <assert.h>
|
|
#include <limits.h>
|
|
#define POW 12
|
|
|
|
long long unsigned hash(char* string);
|
|
void search_pattern_in_text(char* FILE_WAY, char* STRING);
|
|
void get_string(char* string, long long unsigned len);
|
|
|
|
int main() {
|
|
char *FILE_PATH = "rabin_karp.data";
|
|
char* STRING = "Let";
|
|
search_pattern_in_text(FILE_PATH, STRING);
|
|
}
|
|
|
|
long long unsigned hash(char* string) {
|
|
long long unsigned len_string = strlen(string);
|
|
long long unsigned result = 0;
|
|
for (long long unsigned i = 0; i < len_string; i++) {
|
|
result = (result * POW + string[i]) % ULONG_MAX;
|
|
}
|
|
return result;
|
|
}
|
|
void search_pattern_in_text(char *FILE_PATH, char *string) {
|
|
freopen(FILE_PATH, "r", stdin);
|
|
|
|
int c;
|
|
long long unsigned string_len = strlen(string);
|
|
long long unsigned string_hash = hash(string);
|
|
|
|
/* "Текущая" подстрока, её мы будем смещать по тексту */
|
|
char *string_cur = (char*)calloc(string_len + 1, sizeof(char));
|
|
get_string(string_cur, string_len);
|
|
long long unsigned string_cur_hash = hash(string_cur);
|
|
|
|
long long unsigned MAX_POW = 1;
|
|
/* Получаем максимальную степень для элемента строки */
|
|
for (long long unsigned i = 1; i < string_len; i++) {
|
|
MAX_POW = (MAX_POW * POW) % ULONG_MAX;
|
|
}
|
|
|
|
for (long long unsigned i = 0; (c = getchar()) != EOF; i++) {
|
|
/* Проверяем совпадение подстроки посимвольно, чтоб избежать коллизий */
|
|
if (string_hash == string_cur_hash) {
|
|
if (!strcmp(string, string_cur)) {
|
|
printf("%llu\n", i);
|
|
}
|
|
}
|
|
/* Обновляем хеш строки (для следующей подстроки) */
|
|
string_cur_hash = ((string_cur_hash - string_cur[0]*MAX_POW)*POW + c) % ULONG_MAX;
|
|
|
|
/* "Смещаем" подстроку на один символ дальше */
|
|
for (long long unsigned j = 0; j < string_len - 1; j++) {
|
|
string_cur[j] = string_cur[j + 1];
|
|
}
|
|
string_cur[string_len - 1] = c;
|
|
|
|
}
|
|
free(string_cur);
|
|
|
|
fclose(stdin);
|
|
}
|
|
/* Считываем только n символов */
|
|
void get_string(char* string, long long unsigned n) {
|
|
int c;
|
|
for (long long unsigned i = 0; i < n; i++) {
|
|
if ((c = getchar()) != EOF)
|
|
string[i] = c;
|
|
else
|
|
assert(1);
|
|
}
|
|
}
|
|
|
|
|