Cod sursa(job #2045258)

Utilizator JasminaCornesteanJasmina Cornestean JasminaCornestean Data 21 octombrie 2017 23:45:15
Problema Potrivirea sirurilor Scor 14
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*26+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*26)%PRIM; // 26 la puterea n-1
		//deoarece prima cifra din baza 26, transf in baza 10 va fi inmultita cu 26 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*26+H[i+n]-'a')%PRIM; //adaugam ultima, dupa ce inmultim "partea comuna" cu 26
	}
	fo<<k<<'\n';
  for(int i=1; i<=k && i<=1000; i++)
      fo<<nr[i]<<" ";
   //   fo<<w<<" "<<v;
	return 0;
}
//facem trecerea din baza 26 in baza 10

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