Cod sursa(job #679166)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 12 februarie 2012 20:30:24
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<fstream>
#include<string.h>
#include <iostream>
using namespace std;

int nr,pi[2000002],sol[2000],n,m;
char a[2000002],b[2000002];

void match()
{
	int i,w=0;
	nr=0;
	for (i=0;i<m;i++)
	{
		while (b[i]!=a[w] && pi[w]!=0)
			w=pi[w-1];
		if (b[i]==a[w])
			w++;
		
		if (w==n)
		{
			++nr; if (nr<1001) sol[nr]=i;
			w=pi[w-1];
		}
	}
}

void prefix ()
{
	int i;
	pi[0]=0;
	for (i=1;i<n;i++)
	{
		pi[i]=pi[i-1];
		while (a[pi[i]]!=a[i] && pi[i]!=0)
			pi[i]=pi[pi[i]];
	
		if (a[i]==a[pi[i]])
			pi[i]++;
	}
}
			
void citire ()
{
	FILE *f=fopen ("strmatch.in","r");
	fscanf (f,"%s",a);fscanf(f,"%s",b);
	n=strlen(a);m=strlen(b);
	fclose(f);
}

void afisare ()
{
	int i,min;
	FILE *f=fopen ("strmatch.out","w");
	fprintf (f,"%d\n",nr);
	int Min=1000; if (Min>nr) Min=nr;
	for (i=1;i<=Min;i++) 
		fprintf (f,"%d ",sol[i]);
	fclose (f);
	
}

int main ()
{
	citire ();
	prefix();
	match ();
	afisare ();
	return 0;
}