Cod sursa(job #1856284)

Utilizator ArkinyStoica Alex Arkiny Data 24 ianuarie 2017 18:58:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<fstream>
#include<vector>
#include<iostream>
#include<chrono>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;

ofstream out("strmatch.out");

char s1[2000010], s2[2000010];

long long p1 = 0, p2 = 0, p_c1 = 0, p_c2 = 0;

#define MOD1 9319547
#define MOD2 7380157

#define INV1 3106516
#define INV2 4920105

int nr = 0;
vector<int> rez;

int main()
{
	FILE *in = fopen("strmatch.in","r");
	fscanf(in,"%s%s", s2, s1);

	long long l1 = strlen(s1);
	long long l2 = strlen(s2);
	long long pw1 = 1;
	long long pw2 = 1;
	for (int i = 0; i < l2; ++i)
	{
		p1 =(p1 + ((s2[i]) * pw1) % MOD1)%MOD1;
		p2 = (p2 + ((s2[i]) * pw2) % MOD2) % MOD2;

		pw1 = (pw1 * 3) % MOD1;
		pw2 = (pw2 * 3) % MOD2;

	}
	pw1 = 1;
	pw2 = 1;
	for (int i = 0; i < l2; ++i)
	{
		p_c1 = (p_c1 + ((s1[i]) * pw1) % MOD1) % MOD1;
		p_c2 = (p_c2 + ((s1[i]) * pw2) % MOD2) % MOD2;

		if (i != l2 - 1)
		{
			pw1 = (pw1 * 3) % MOD1;
			pw2 = (pw2 * 3) % MOD2;
		}

	}



	if (p1 == p_c1 && p2 == p_c2)
	{
		rez.push_back(0);
		++nr;
	}

	for (int i = l2; i < l1; ++i)
	{
		p_c1 = ((((MOD1 + p_c1 - s1[i - l2])%MOD1) * INV1)%MOD1 + (s1[i] * pw1)%MOD1)%MOD1;
		p_c2 = ((((MOD2 + p_c2 - s1[i - l2])%MOD2) * INV2)%MOD2+ (s1[i] * pw2) % MOD2) % MOD2;

		if (p1 == p_c1 && p2 == p_c2)
		{
			++nr;
			if(nr<=1000)
				rez.push_back(i-l2+1);
		}

	}
	
	out << nr << "\n";

	for (int i = 0; i < rez.size(); ++i)
		out << rez[i] << " ";

	return 0;
}