Cod sursa(job #807152)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 4 noiembrie 2012 11:26:17
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char PAT[2000000];
char TEX[2000000];
char S[4000000];
char T[1000];
int Z[4000000];
int l,r,n,i,p,q;
int k,kp;
int lung,rez;
int main()
{
	f.getline(PAT,2000000);
	lung=strlen(PAT);
	f.getline(TEX,2000000);	
	n=strlen(PAT)+strlen(TEX)+1;
	S[0]='$';
	S[1]='\0';
	strcat(S,PAT);
	strcat(S,"$");
	strcat(S,TEX);
	strcat(S,"$");
	// se calculeaza Z[2];
	k=2;
	i=1;
	while (S[k]==S[i])
	{
		k++;
		i++;
	}
	Z[2]=i-1;
	r=Z[2];
	l=1;
	// se calculeaza Z[k]
	for (k=3;k<=n;k++)
		if (k>r)
		{
			p=k;
			i=1;
			while (S[p]==S[i])
			{
				p++;
				i++;
			}
			Z[k]=i-1;
			r=Z[k];
			l=k;
		}
		else
		{
			kp=k-l+1;
			if (Z[kp]<r-k+1)
				Z[k]=Z[kp];
			else
			{
				q=k;
				i=1;
				while (S[q]==S[i])
				{
					q++;
					i++;
				}
				Z[k]=q-k;
				r=q-1;
				l=k;
			}
		}
	rez=0;
	for (i=1;i<=n;i++)
		if (Z[i]==lung)
			rez++;
	g<<rez<<'\n';
	for (i=1;i<=n;i++)
		if (Z[i]==lung)
			g<<i-lung-2<<" ";
		f.close();
		g.close();
	return 0;
}