Cod sursa(job #728684)

Utilizator vld7Campeanu Vlad vld7 Data 28 martie 2012 21:23:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream.h>
#include <string.h>

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

int Urm[2000001];
char T[2000001];	// textul
char P[2000001];	// patternu'
int n, m, NrSol, SOL[2000001];

void Urmatorul()
{
	int k=-1, x;
	Urm[0]=0;
	for(x=1;x<m;x++)
	{
		while (k>0 && P[k+1]!=P[x])
			k=Urm[k];
		if (P[k+1]==P[x])
			k++;
		Urm[x]=k;
	}
}

int main()
{
	int i, x=-1;
	f.getline(P, 2000001);	f.getline(T, 2000001);
	n=strlen(T);	m=strlen(P);
	Urmatorul();			// am facut functia prefix
	
	for (i=0; i<n; i++)
	{
		while (x>0 && P[x+1]!=T[i])
			x=Urm[x];
		if (P[x+1]==T[i])		// am mai gasit un caracter corect
			x++;
		if (x==m-1)
		{
			SOL[++NrSol]=i-x;
			x=Urm[x];
		}
	}
	
	g<<NrSol<<'\n';
	for(i=1;i<=NrSol;i++)
		g<<SOL[i]<<" ";
	
	f.close();
	g.close();
	
	
	return 0;
}