Cod sursa(job #629768)

Utilizator ml.vladareanVladarean Maria ml.vladarean Data 3 noiembrie 2011 22:34:20
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int B=67;
const int P=666013;
string S1,S2;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int nrpoz=0;
int nrAp=0;

vector<int> Poz;

void Read()
{
	fin>>S1>>S2;
}

int putereB()
{
	int aux=1;
	int s = S1.size();
	for(int i=1; i<= s;i++)
		aux=(aux*B)%P;
	return aux;
}

void S1Baza()
{	
	int poz;
	int Ha=S1[0],Hb=S2[0];
	int sizeS1=S1.size(),sizeS2=S2.size();
	int putere=putereB();

	for(int i=1;i<sizeS1;i++)
	{
		Ha=((Ha*B)%P + S1[i])%P;

		Hb=((Hb*B)%P + S2[i])%P;
	}
	int flag=1,j,l;
	if(Hb==Ha)
		{			
			for(j=0;j<sizeS1;j++)
				if(S1[j]!=S2[j])
				{
					flag=0;
					break;
				}
			if (flag)
				Poz.push_back(0);
	}
	int k=0;
	while (k != (sizeS2-sizeS1))
	{
		Hb = (P + Hb - (S2[k] * putere) % P) % P;
		Hb = (Hb * B ) % P;
		Hb = (Hb + S2[k + sizeS1 ]) % P;
		k++;
		if(Hb==Ha)
		{
			flag=1;
			for(l=0,j=k;j<=k+sizeS1-1 && l<sizeS1;j++,l++)
				if(S1[l]!=S2[j])
				{
					flag=0;
					break;
				}
			if (flag)
				Poz.push_back(k);
		}
	}
}

int main()
{

	Read();
	S1Baza();
	int k = Poz.size();
	fout<<k<<"\n";
	int minim = min( 1000,k);
	for(int i=0;i<minim;i++)
		fout<<Poz[i]<<" ";
	fout<<"\n";
	return 0;
}