Cod sursa(job #668099)

Utilizator laurionLaurentiu Ion laurion Data 24 ianuarie 2012 13:22:08
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<fstream>
#include<iostream>
#include<vector>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

#define baza 73
#define mod1 100007
#define mod2 100021

vector<int> matches;
string sir, subsir;
int hashSir1=0,hashSir2=0,hashSubsir1=0,hashSubsir2=0,baza_n1=1,baza_n2=1;

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

	getline(fin,subsir);
	getline(fin,sir);
	//cerr<<sir<<'\n'<<subsir;
	if (sir.size()<subsir.size())
	{
		fout<<0<<'\n';
		return 0;
	}

	for(int i=0;i<subsir.length();++i)
	{
		hashSubsir1=(hashSubsir1*baza+subsir[i])%mod1;
		hashSubsir2=(hashSubsir2*baza+subsir[i])%mod2;
		hashSir1=(hashSir1*baza+sir[i])%mod1;
		hashSir2=(hashSir2*baza+sir[i])%mod2;
		if(i>0)
		{
			baza_n1=(baza_n1*baza)%mod1;
			baza_n2=(baza_n2*baza)%mod2;
		}
	}

	if(hashSir1==hashSubsir1 && hashSir2==hashSubsir2)
	{
		matches.push_back(1);
	}

	for(int i=subsir.length();i<sir.length();++i)
	{
		hashSir1=((hashSir1-(sir[i-subsir.length()]*baza_n1)%mod1+mod1)*baza + sir[i])%mod1;
		hashSir2=((hashSir2-(sir[i-subsir.length()]*baza_n2)%mod2+mod2)*baza + sir[i])%mod2;
		if(hashSir1==hashSubsir1 && hashSir2==hashSubsir2)
		{
			matches.push_back(i-subsir.length()+1);
		}
	}
	fout<<matches.size()<<'\n';
	for(int i=0;i<matches.size();++i)
	{
		fout<<matches[i]<<' ';
	}
	fout<<'\n';
	fout.close();
	return 0;
}