Cod sursa(job #1727845)

Utilizator ArkinyStoica Alex Arkiny Data 11 iulie 2016 19:01:04
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
using namespace std;

#define P 73
#define MOD1 100007
#define MOD2 100021


int h1, h2,he1,he2;

char s1[2000010], s2[2000010];

int a[1010],nr;

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

int main()
{
	int l1, l2;

	in >> s1 >> s2;

	l1 = strlen(s1);
	l2 = strlen(s2);
	
	int p1=1, p2=1;

	for (int i = 0;i < l1;++i)
	{
		h1 = (h1*P + s1[i]) % MOD1;
		h2 = (h2*P + s1[i]) % MOD2;

		if (i)
		{
			p1 = (p1*P) % MOD1;
			p2 = (p2*P) % MOD2;
		}
	}
	for (int i = 0;i < l1;++i)
	{
		he1 = (he1*P + s2[i]) % MOD1;
		he2 = (he2*P + s2[i]) % MOD2;
	}

	if (h1 == he1 && h2 == he2)
		a[++nr] = 0;

	for (int i = 1;i <= l2-l1;++i)
	{
		he1 = (((he1 - (s2[i-1] *p1 )%MOD1 + MOD1)*P)%MOD1 + s2[i+l1-1]) % MOD1;
		he2 = (((he2 - (s2[i - 1] * p2) % MOD2 + MOD2)*P)%MOD2 + s2[i+l1-1]) % MOD2;
		if (h1 == he1 && h2 == he2)
		{
			++nr;
			if (nr <= 1000)
				a[nr] = i;
		}
	}
	out << nr << '\n';
	for (int i = 1;i <= nr && i <= 1000;++i)
		out << a[i] << " ";


	

	return 0;
}