Cod sursa(job #520832)

Utilizator tudorsTudor Siminic tudors Data 10 ianuarie 2011 16:32:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
long m,n,p,k,i,rez,q,t;
long L[2000000],REZ[2000000];;
char A[2000000],B[2000000];

FILE *fin=fopen("strmatch.in","r");
FILE *fout=fopen("strmatch.out","w");

int main()
{	
	fscanf(fin,"%s %s",A,B);
	fclose(fin);
	
	n=strlen(A);
	m=strlen(B);
	
	for (i=n+1;i>=1;i--)
		A[i]=A[i-1];
	for (i=m+1;i>=1;i--)
		B[i]=B[i-1];
	
	L[1]=0;
	for (p=2;p<=n;p++)
	{
		k=L[p-1];
		while (k>0 && A[p]!=A[k+1])
			k=L[k];
		if (A[k+1]==A[p])
			k++;
		L[p]=k;
	}
	
	rez=0;
	k=0;
	for (t=1;t<=m;t++)
	{
		while (k>0 && B[t]!=A[k+1])
			k=L[k];
		if (A[k+1]==B[t])
			k++;
		if (k==n)
		{
			rez++;
			REZ[rez]=t-k;
		}
	}

	fprintf(fout,"%ld\n",rez);
	if (rez>1000)
		rez=1000;
	for (i=1;i<=rez;i++)
		fprintf(fout,"%d ",REZ[i]);
	fclose(fout);
	return 0;
}