Cod sursa(job #599481)

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

#define lsir 2000000
#define mod 100007
#define baza 73

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

char a[lsir], b[lsir];
int hPattern, hash1, pBaza, nr, poz[lsir], la, lb;

int verifica(int start)
{
	for(int i = 0; i < la; i++)
		if(a[i] != b[start + i])
			return 0;
	return 1;
}

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

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

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

	pBaza = 1;
	for(int i = 0; i < la; i++)
	{
		hPattern = (hPattern * baza + a[i]) % mod;

		if(i != 0)
		{
			pBaza = (pBaza * baza) % mod;
		}
	}

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

	
	if(hash1 == hPattern && verifica(0) == 1)
	{
		nr++;
		poz[0] = 1;
	}

	for(int i = la; i < lb; i++)
	{
		hash1 = ((hash1 - (b[i-la] * pBaza) % mod + mod) * baza + b[i]) % mod;

		if(hash1 == hPattern && verifica(i-la+1) == 1)
		{
			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;
}