Cod sursa(job #984370)

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

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

long long power(long long x, unsigned a)
{
    if(a == 0) return 1;
    if(a == 1) return x % MOD;
    if(a % 2 == 0) return (power((x * x) % MOD, a / 2)) % MOD;
    return (x * power((x * x) % MOD, a / 2)) % MOD;
}

long long getHash(char *str, int a)
{
	long long ret = 0;
	for(int i = 0; i < a; i++)
		ret = (ret * pb + str[i]) % 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 comp = getHash(str, strlen(str)), to = getHash(strl, strlen(str)), pow = power(pb, strlen(str));
	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;
}