Cod sursa(job #1805676)

Utilizator ArkinyStoica Alex Arkiny Data 14 noiembrie 2016 00:43:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
#include<string.h>
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;
}