Cod sursa(job #195005)

Utilizator stefysStefan stefys Data 15 iunie 2008 20:55:33
Problema Potrivirea sirurilor Scor 38
Compilator c Status done
Runda Arhiva educationala Marime 2.08 kb
#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;
}