Cod sursa(job #2045404)

Utilizator JasminaCornesteanJasmina Cornestean JasminaCornestean Data 22 octombrie 2017 12:52:10
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <string.h>
#define PRIM 1000003
using namespace std;

ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

char N[2000001],H[2000001];
long long n,h,v,w,nr[1001];
long long p,k;

int valoare(char A[],int st,int dr)
{
	int rez;
	rez=0;
	for (int i=st;i<=dr;i++)
		rez=(rez*58+A[i]-'A')%PRIM; //cu schema lui Horner
	return rez;
}

int main()
{
	fi>>N+1;
	fi>>H+1;
	n=strlen(N+1);
	h=strlen(H+1);
	w=valoare(N,1,n); //valoarea lui needle
	v=valoare(H,1,n); //valoarea primei secvente din Haystack
	p=1;
	for (int i=1;i<=n-1;i++)
		p=(p*58)%PRIM; // 58 la puterea n-1
		//deoarece prima cifra din baza 58, transf in baza 10 va fi inmultita cu 58 la puterea n-1
	for (int i=1;i<=h-n+1;i++)
	{
		if (v==w)
		{
		   k++;
		   if( k<=1000)
        nr[k]=i;
    }
		/// trecere cu un caracter spre dreapta
		v=(PRIM+v-((H[i]-'A')*p)%PRIM)%PRIM; //scadem prima cifra
		v=(v*58+H[i+n]-'A')%PRIM; //adaugam ultima, dupa ce inmultim "partea comuna" cu 58
	}
	fo<<k<<'\n';
  for(int i=1; i<=k && i<=1000; i++)
      fo<<nr[i]-1<<" ";
     // fo<<w<<" "<<v;
	return 0;
}
//facem trecerea din baza 58 in baza 10

//avem si litere mari si mici, facem altcumva, alta baza