Cod sursa(job #1049967)

Utilizator rvnzphrvnzph rvnzph Data 7 decembrie 2013 23:00:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
//Rabin-Karp
#include <stdio.h>
#include <cstring>
#include <vector>

using namespace std;

const int strLEN=2000002;
const int BASE=79;
const int MOD1=999983;
const int MOD2=999979;

char A[2000002],B[2000002];
vector <int> sol;

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	fgets(A,strLEN,stdin);
	fgets(B,strLEN,stdin);

	int nA=strlen(A)-1;
	int nB=strlen(B)-1;

	int hashA1,hashA2,hashB1,hashB2;
	hashA1=hashA2=hashB1=hashB2=0;

	int pow1,pow2;
	pow1=pow2=1;

	for(int i=0;i<nA;++i)
	{
		hashA1=(hashA1*BASE+A[i]-'0')%MOD1;
		hashA2=(hashA2*BASE+A[i]-'0')%MOD2;
		
		hashB1=(hashB1*BASE+B[i]-'0')%MOD1;
		hashB2=(hashB2*BASE+B[i]-'0')%MOD2;

		pow1=(pow1*BASE)%MOD1;
		pow2=(pow2*BASE)%MOD2;
	}

	if(hashA1==hashB1&&hashA2==hashB2) sol.push_back(0);

	for(int i=nA;i<nB;++i)
	{
		hashB1=((hashB1*BASE+B[i]-'0')%MOD1+MOD1-(pow1*(B[i-nA]-'0'))%MOD1)%MOD1;
		hashB2=((hashB2*BASE+B[i]-'0')%MOD2+MOD2-(pow2*(B[i-nA]-'0'))%MOD2)%MOD2;

		if(hashA1==hashB1&&hashA2==hashB2) sol.push_back(i-nA+1);
	}

	printf("%zu\n",sol.size());
	for(vector <int>::iterator it=sol.begin();it!=sol.end()&&it-sol.begin()<=1000;++it)
		printf("%d ",*it);
	printf("\n");

	return 0;
}