Cod sursa(job #430881)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 31 martie 2010 13:58:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream.h>
#include<string.h>

char s1[2000002],s2[2000002];

int n,m,nr,v[1005],pi[2000002];

void afisare ()
{
	ofstream g("strmatch.out");
	g<<nr<<'\n';
	for (int i=1;i<=nr;i++)
		g<<v[i]<<' ';
	g.close();
}

void kmp ()
{
	int i,j;
	j=0;
	for (i=0;i<n && nr<1000;i++)
	{
		while (j>0 && s1[i]!=s2[j+1])
			j=pi[j];
		if (s1[i]==s2[j+1])
			j++;
		if (j==m-1)
			v[++nr]=i-m+2,j=pi[j];
	}
}
			

void prefix ()
{
	int i,j;
	for (i=2;i<m;i++)
	{
		j=pi[i-1];
		while (j>0 && s2[j+1]!=s2[i])
			j=pi[j];
		if (s2[j+1]==s2[i])
			j++;
		pi[i]=j;
	}
}

void citire ()
{
	ifstream f ("strmatch.in");
	f>>s1;
	s2[0]='#';
	s2[1]=0;
	strcat(s2,s1);
	f>>s1;
	n=strlen(s1);
	m=strlen(s2);
	f.close();
}

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