| Код |
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX_SUBSTR_LEN 10
long powerTable[MAX_SUBSTR_LEN] = {0};
void initPowerTable()
{
for (int i = 0; i < MAX_SUBSTR_LEN; i++)
{
powerTable[i] = pow('z', i);
}
}
long int hash(const char * str, unsigned int str_len)
{
long result = 0;
for (int i = 0; i < str_len; i++)
{
result += str[i] * powerTable[i];
}
return result;
}
int RabinKarp(const char * str, const char * substr)
{
int i, j;
long subh = hash(substr, strlen(substr));
long sh = hash(str, strlen(substr));
for (i = 0; i < strlen(str) - strlen(substr); i++)
{
if(subh == sh)
{
return i;
}
// calculate new hash
sh /= 'z';
sh += powerTable[strlen(substr) - 1] * str[i + strlen(substr) ];
}
return -1;
}
void main()
{
initPowerTable();
printf("%d", RabinKarp("AA BLA AAA", "BLA"));
}
|
Уберите только эти бесконечные вызовы strlen()  ) Ну и для слишком длинных подстрок, когда хэш становится вырожденным добавьте проверку strncmp() еще |