Cod sursa(job #195113)

Utilizator stefysStefan stefys Data 16 iunie 2008 19:31:39
Problema Potrivirea sirurilor Scor 38
Compilator c Status done
Runda Arhiva educationala Marime 2.24 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;
}

inline void nonewline (char *p)
{
	for (; *p; ++p) if (*p == '\r' || *p == '\n') { *p = '\0'; break; }
}

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+3);
	substr = malloc(MAXSIZE+3);
	
	fgets(substr, MAXSIZE+3, stdin); nonewline(substr);
	fgets(str, MAXSIZE+3, stdin); nonewline(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_array_size < 1000 && (offset = RabinKarp(&info)) != -1) {
		absoluteoffset += offset+1;
		offset_array[offset_array_size++] = absoluteoffset-1;
		info.str += offset+1;
		info.str_size -= offset+1;
	}
	
	printf("%u\n", offset_array_size);
	
	for (i=0; i<offset_array_size; ++i)
		printf("%u ", offset_array[i]);
	printf("\n");
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}