Cod sursa(job #984373)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 14 august 2013 12:32:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <cstdio>
#include <iostream>
#include <cstring>

const int pb = 257;
const int MOD = 1000000007;

long long getHash(char *str, int a, long long& power)
{
	power = 1;
	long long ret = 0;
	for(int i = 0; i < a; i++)
		ret = (ret * pb + str[i]) % MOD, power = (power * pb) % MOD;
	return ret;
}

bool compare(char *str, char *strl, int delay, int start)
{
	for(unsigned i = 0; i < start; i++)
		if(str[i] != strl[delay + i]) return false;
	return true;
}

unsigned rabin(char *str, char *strl, int *nArr)
{
	unsigned nr = 0, a = strlen(str), b = strlen(strl);
	long long pow = 1;
	long long comp = getHash(str, strlen(str), pow), to = getHash(strl, strlen(str), pow);
	if(comp == to)
	{
		if(compare(str, strl, 0, a))
		{
			nArr[nr] = 0;
			nr++;
		}
	}
	for(int i = a; i < b; i++)
	{
		to = to * pb + strl[i];
		to %= MOD;
		to -= (pow * strl[i - a]) % MOD;
		if(to < 0) to += MOD;
		if(comp == to)
		{
			if(compare(str, strl, i - a + 1, a)) 
			{
				if(nr < 1000) nArr[nr] = i - a + 1;
				nr++;
			}
		}
	}
	return nr;
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	char *str = new char[2000000], *strl = new char[2000000];
	int *nArr = new int[1000];
	gets(str);
	gets(strl);
	int nr = rabin(str, strl, nArr), a;
	printf("%d \n", nr);
	if(nr < 1000) a = nr;
	else a = 1000;
	for(int i = 0; i < a; i++)
		printf("%d ", nArr[i]);
	return 0;
}