Cod sursa(job #599482)

Utilizator igsifvevc avb igsi Data 28 iunie 2011 21:25:38
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <string>
using namespace std;

#define lsir 2000000
#define mod1 200000
#define mod2 170000
#define baza 101

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[lsir], b[lsir];
int hPattern1, hPattern2, hash1, hash2, pBaza1, pBaza2, nr, poz[lsir];

int main()
{
	fin >> a >> b;

	int la, lb;

	la = strlen(a);
	lb = strlen(b);

	if(la > lb)
	{
		fout << "0\n";
		return 0;
	}

	pBaza1 = pBaza2 = 1;
	for(int i = 0; i < la; i++)
	{
		hPattern1 = (hPattern1 * baza + a[i]) % mod1;
		hPattern2 = (hPattern2 * baza + a[i]) % mod2;

		if(i != 0)
		{
			pBaza1 = (pBaza1 * baza) % mod1;
			pBaza2 = (pBaza2 * baza) % mod2;
		}
	}

	for(int i = 0; i < la; i++)
	{
		hash1 = (hash1 * baza + b[i]) % mod1;
		hash2 = (hash2 * baza + b[i]) % mod2;
	}

	
	if(hash1 == hPattern1 && hash2 == hPattern2)
	{
		nr++;
		poz[0] = 1;
	}

	for(int i = la; i < lb; i++)
	{
		hash1 = ((hash1 - (b[i-la] * pBaza1) % mod1 + mod1) * baza + b[i]) % mod1;
		hash2 = ((hash2 - (b[i-la] * pBaza2) % mod2 + mod2) * baza + b[i]) % mod2;

		if(hash1 == hPattern1 && hash2 == hPattern2)
		{
			nr++;
			poz[i - la + 1] = 1;
		}
	}

	fout << nr << '\n';
	nr = 0;
	for(int i = 0; i < lb && nr < 1000; i++)
		if(poz[i] == 1)
			fout << i << ' ',nr++;
	fout << '\n';

	fin.close();
	fout.close();
	return 0;
}