Cod sursa(job #446122)

Utilizator voikybodea voichita voiky Data 25 aprilie 2010 08:52:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream.h>
#include<string.h>

char a[2000001],b[2000001];
int urm[2000000],poz[1001],k;
ofstream g("strmatch.out");

void init_urm(char *a) 
{ 
	int i=0,j=-1,la=strlen(a); 
	urm[0] = -1; 
	while(i<la)
	{
		while(j>-1 && a[i]!=a[j])j=urm[j];
		i++;j++;
		if(a[i]==a[j])urm[i]=urm[j];
		else urm[i]=j;
	}
} 

void cauta(char *a, char *b) 
{ 
	init_urm(a);
	int i=0, j=0, la = strlen(a), lb = strlen(b); 
	while(j<lb)
	{
		while(i>-1 && a[i]!=b[j])i=urm[i];
		i++;j++;
		if(i>=la)
		{
			poz[++k]=j-i;
			i=urm[i];
		}
	}
}

int main()
{
	ifstream f("strmatch.in");
	f.get(a,2000001);f.get();f.get(b,2000001);
	cauta(a,b);
	g<<k<<'\n';
	for(int i=1;i<=k;i++)g<<poz[i]<<' ';
	f.close();g.close();
	return 0;
}