Cod sursa(job #1856285)

Utilizator ArkinyStoica Alex Arkiny Data 24 ianuarie 2017 19:00:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 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];

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

#define MOD1 60169
#define MOD2 59497

#define INV1 24727
#define INV2 29341

unsigned  int nr = 0;
vector<unsigned  int> rez;

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

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

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

	}
	pw1 = 1;
	pw2 = 1;
	for (unsigned 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 * 73) % MOD1;
			pw2 = (pw2 * 73) % MOD2;
		}

	}



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

	for (unsigned 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 (unsigned int i = 0; i < rez.size(); ++i)
		out << rez[i] << " ";

	return 0;
}