Pagini recente » Cod sursa (job #985214) | Cod sursa (job #2155351) | Cod sursa (job #1603618) | Cod sursa (job #659868) | Cod sursa (job #195005)
Cod sursa(job #195005)
#include <stdio.h>
#include <string.h>
#define MAXSIZE 2000000
#define MOD (1<<10)
#define C 17
typedef struct RabinKarp_info {
const char *str, *substr;
unsigned int str_size, substr_hash, substr_size;
} RabinKarp_info;
inline unsigned int RabinKarp_rolling_hash (const char *s, unsigned int size)
{
unsigned int ret=0, i;
for (i=0; i<size; ++i) ret = (ret+C*s[i])%MOD;
return ret;
}
inline unsigned int RabinKarp_hashroll (unsigned int hash, char add, char del)
{ return (hash+C*(add-del))%MOD; }
unsigned int RabinKarp (RabinKarp_info *info)
{
unsigned int str_hash = RabinKarp_rolling_hash(info->str, info->substr_size), offset, maxoffset;
if (str_hash == info->substr_hash && strncmp(info->str, info->substr, info->substr_size)==0) return 0;
maxoffset = info->str_size - info->substr_size + 1;
for (offset = 1; offset < maxoffset; ++offset) {
str_hash = RabinKarp_hashroll(str_hash, info->str[offset + info->substr_size -1], info->str[offset-1]);
if (str_hash == info->substr_hash && strncmp(info->str+offset, info->substr, info->substr_size)==0)
return offset;
}
return -1;
}
int main (void)
{
char *str, *substr;
unsigned int offset, absoluteoffset=0, offset_array[1000], offset_array_size=0, i;
RabinKarp_info info;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w+", stdout);
str = malloc(MAXSIZE+1);
substr = malloc(MAXSIZE+1);
scanf("%s\n", substr);
scanf("%s\n", str);
info.substr_size = strlen(substr);
info.substr_hash = RabinKarp_rolling_hash(substr, info.substr_size);
info.str_size = strlen(str);
info.str = str;
info.substr = substr;
while ( info.str_size>info.substr_size && (offset = RabinKarp(&info)) != -1) {
absoluteoffset += offset+1;
offset_array[offset_array_size++] = absoluteoffset-1;
info.str += offset+1;
info.str_size -= offset+1;
if (offset_array_size == 1000) break;
}
printf("%u\n", offset_array_size);
for (i=0; i<offset_array_size; ++i)
printf("%u ", offset_array[i]);
fclose(stdin);
fclose(stdout);
return 0;
}