Cod sursa(job #2344403)

Utilizator AndreiGSGhiurtu Andrei AndreiGS Data 15 februarie 2019 08:20:39
Problema Potrivirea sirurilor Scor 96
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int ap[1001], k;

void getZarr(string str, int Z[]);

void search(string text, string pattern, int &matches)
{
  //concateneaza pat cu txt
	string concat=pattern+"$"+text;
	int l=concat.length();

	//construieste vectorul Z
	int Z[l];
	getZarr(concat, Z);

	//verificam match-urile
	for(int i=0; i<l; ++i)
	{
		//daca z[i] == lungimea pat am gasit un match
		if(Z[i]==pattern.length())
		{
      matches++;
      if(k<1000)
        ap[k++]=i-pattern.length()-1;
    }
	}
}

//Construieste Z
void getZarr(string str, int Z[])
{
	int n=str.length();
	int L, R, k;

	L=R=0;
	for(int i=1; i<n; ++i)
	{
		// if i>R nimic nu se "match-uieste"
		if(i>R)
		{
			L=R=i;
			while(R<n && str[R-L]==str[R])
				R++;
			Z[i]=R-L;
			R--;
		}
		else
		{
			k=i-L;
			if(Z[k]<R-i+1)
				Z[i]=Z[k];
			else
			{
				L=i;
				while(R<n && str[R-L]==str[R])
					R++;
				Z[i]=R-L;
				R--;
			}
		}
	}
}

int main()
{
  int matches=0;
	string pat, text;
  getline(f, pat);
  getline(f, text);
	search(text, pat, matches);
  g<<matches<<'\n';
  for(int i=0; i<k; ++i)
    g<<ap[i]<<' ';
	return 0;
}