Cod sursa(job #2040480)

Utilizator JasminaCornesteanJasmina Cornestean JasminaCornestean Data 15 octombrie 2017 20:51:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <string.h>
using namespace std;

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

char N[2000001],H[2000001],c;
int S[2000001],p[1001];
int n,h,k,f,nr,i;
int main()
{
	fi>>N+1;
	n=strlen(N+1);
	/// se construieste sirul S
	S[0]=-1;
	S[1]=0;
	for ( i=2;i<=n;i++)
	{
		/// se calculeaza S[i]
		k=i-1; //merg la ala din spate prima data
		c=N[i]; //sa vad care trece de caracteru i din needle
		while (N[S[k]+1]!=c && S[k]!=-1)  // cat timp niciunu nu trece de caracteru c
			k=S[k];//tot mergem la predecesor. se iese din while cand am gasit
		S[i]=S[k]+1; //cel mai din dreapta predecesor pentru lemmingul i este cel de pe ultima poz verificata+1
	}
	fi>>H;
	h=strlen(H);
	/// algoritmul KMP
	f=0;
	for (i=0; i<h; i++) //rostim fiecare litera din H
	{
		/// bucla while pentru a detecta cel mai dinspre dreapta
		/// lemming supravietuitor literei H[i]
		while (f!=-1)//cat timp n-am ajuns la inceputul sirului
		{
			if (N[f+1]==H[i])
				break; //a supravietuit
			f=S[f]; //n-a supravietuit si ne intereseaza cine era inaintea lui
		}
		if (f==-1)
			f=0; // nu supravietuieste niciunul si reluam algoritmul de la inceput, doar ca
          // continuam cu rostirea literei i+1
		else
		{
			f++; //trece de litera H[i]
			if (f==n) //a ajuns la finalul lui needle
			{
			  nr++;
			  if( nr<=1000)
				    p[nr]=i-n+1;
				f=S[f]; //reluam de la cel din dreapta
			}
		}
	}
	fo<<nr<<'\n';
	for( i=1; i<=nr && i<=1000; i++)
      fo<<p[i]<<" ";
	return 0;
}