Cod sursa(job #629759)

Utilizator ml.vladareanVladarean Maria ml.vladarean Data 3 noiembrie 2011 22:12:43
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <string>


using namespace std;

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



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

int putereB()
{
	int aux=1;
	for(int i=1;i<=S1.size()-1;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;
	}
	
	for(int i=1;i<sizeS1;i++)
	{
		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[nrpoz++]=0;
			nrAp++;
	}
	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[nrpoz++]=k;
			nrAp++;
		}
	}
}

int main()
{

	Read();
	S1Baza();
	fout<<nrAp<<"\n";
	for(int i=0;i<nrpoz;i++)
		fout<<Poz[i]<<" ";
	

	return 0;
}