Cod sursa(job #2045411)

Utilizator JasminaCornesteanJasmina Cornestean JasminaCornestean Data 22 octombrie 2017 12:59:30
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 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,c;
bool nu;

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)
		{
		   //verificam
		   nu=0; c=0;
		   for( int j=i; j<i+n; j++)
           if( H[j]!=N[++c] )
           {
             nu=1;
             break;
           }
       if( nu==0)
       {
           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