Cod sursa(job #1856276)

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

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

char s1[2000010], s2[2000010];

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

#define MOD1 34919
#define MOD2 41593

#define INV1 11640
#define INV2 27729

int nr = 0;
vector<int> rez;

int main()
{
	in >> s2 >> s1;

	int l1 = strlen(s1);
	int l2 = strlen(s2);
	int pw1 = 1;
	int 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;
}