#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const long long int M = 1e9 + 21;
const long long int P = 2027;
void degreesP(long long int p, long long int m, int n, long long int* degrees)
{
degrees[0] = 1;
for (int i = 1; i < n; i++)
{
degrees[i] = ( degrees[i - 1] * (long long) p) % m;
}
}
long long int polynomHash(char* s1, int len, long long int* degrees, long long int m)
{
long long int hash = 0;
for (int i = 0; i < len; i++)
{
hash = (hash * degrees[1]) % m;
hash += (((long long) s1[i]));
hash %= m;
}
return hash;
}
void rabinKarp(char* s1, char* s2, int len_s1, int len_s2, long long int* degrees, long long int m)
{
long long int hash1 = polynomHash(s1, len_s2, degrees, m);
long long int hash2 = polynomHash(s2, len_s2, degrees, m);
int raz = len_s1 - len_s2;
for (int i = len_s2; i <= len_s1; i++)
{
if (hash1 == hash2)
{
if (!strncmp(s1 + i - len_s2, s2, len_s2))
{
//printf("1");
//putchar('E');
printf("%d\n", i - len_s2);
}
}
hash1 = (((hash1 * degrees[1] % m - degrees[len_s2] * s1[i - len_s2]
+ s1[i])% m) + m) % m;
}
return;
}
int main()
{
//printf("sdc");
char* s1 = (char*) calloc(5 * 10000 + 2, sizeof(char));
char* s2 = (char*) calloc(5 * 10000 + 2, sizeof(char));
//printf("dsc1\n");
scanf("%s", s1);
scanf("%s", s2);
//printf("dsc2\n");
int len_s1 = strlen(s1);
int len_s2 = strlen(s2);
if (len_s1 < len_s2)
{
return 0;
}
long long int* degrees = (long long int*) calloc(len_s1, sizeof(int));
degreesP(P, M, len_s1, degrees);
//printf("sdd4\n");
rabinKarp(s1, s2, len_s1, len_s2, degrees, M);
//printf("opdop\n");
free(degrees);
free(s1);
free(s2);
//printf("sdcvdsf\n");
}
/*
abracadabra
ra
*/
Почему когда строка в main "printf("sdc")" закоментирована, то возникает "malloc(): corrupted top size", а когда незакомментирована то этой ошибки нет?
