Cod sursa(job #2720471)

Utilizator FrostfireMagirescu Tudor Frostfire Data 10 martie 2021 21:17:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <vector>
#define ll long long
#define B 74
#define NMAX 2000000
#define MOD1 666017
#define MOD2 666019

using namespace std;

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

string s1, s2;
ll H1, H2, h1, h2, putB_1, putB_2, ans;
vector <int> v;

int main()
{
	fin >> s1 >> s2;
	int len1 = s1.size(), len2 = s2.size();
	putB_1 = putB_2 = 1;
	for(int i=1; i<len1; i++)
		{	putB_1 = putB_1 * B % MOD1;
			putB_2 = putB_2 * B % MOD2;
		}
	for(int i=0; i<len1; i++)
		{	H1 = (H1 * B + (s1[i] - '0')) % MOD1;
			H2 = (H2 * B + (s1[i] - '0')) % MOD2;
		}
	for(int i=0; i<len1-1; i++)
		{	h1 = (h1 * B + (s2[i] - '0')) % MOD1;
			h2 = (h2 * B + (s2[i] - '0')) % MOD2;
		}
	for(int i=len1-1; i<len2; i++)
		{	h1 = (h1 * B + (s2[i] - '0')) % MOD1;
			h2 = (h2 * B + (s2[i] - '0')) % MOD2;
			if(h1 == H1 && h2 == H2)
				{	ans++;
					if(v.size() < 1000)
						v.push_back(i - len1 + 1);
				}
			h1 = (h1 - putB_1 * (s2[i-len1+1] - '0') % MOD1 + MOD1) % MOD1;
			h2 = (h2 - putB_2 * (s2[i-len1+1] - '0') % MOD2 + MOD2) % MOD2;
		}
	fout << ans << '\n';
	for(auto u : v)
		fout << u << ' ';
	fout << '\n';
	return 0;
}