Cod sursa(job #467486)

Utilizator whoasdas dasdas who Data 29 iunie 2010 00:53:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
/*  p[] - pattern, t[] - text
	numerotam de la 1. k reprezinta lungimea prefixului-sufix maxim la pasul curent 
	si e salvat in vectorul pi[]. Exemplu:
											ababbababaac
											001201234310            */

#include<string>
#include<fstream>
using namespace std;
fstream f("strmatch.in",ios::in),g("strmatch.out",ios::out);

char p[2000002],t[2000002];
long pi[2000002],m,n,nrap,aparitii[1001];
void citire()
{
	
    
	f.get( p+1, 2000001 ); f.get();
	f.get( t+1, 2000001 );
	n = strlen( t+1 );
	m = strlen( p+1 );
	nrap=0;
}

void calc_prefix()
{
	int k=0;
	pi[1]=0;
	
	for(int i=2;i<=m;i++)
	{
		while((k>0)&&(p[k+1]!=p[i]))
			k=pi[k];
		if(p[k+1]==p[i])
			k++;
		pi[i]=k;
	}
}

void kmp()
{
	int k=0;
	
	for(int i=1;i<=n;i++)
	{
		while((k>0)&&(p[k+1]!=t[i]))
			k=pi[k];
		if(p[k+1]==t[i])
			k++;
		if(k==m)
		{
			k=pi[k];
			++nrap;
			if(nrap<=1000) 
				aparitii[nrap]=i-m;
		}
	}

}

void afisare()
{
	g<<nrap<<"\n";
	for(int i=1;i<=nrap;i++)
		g<<aparitii[i]<<" ";
}
int main()
{
	citire();
	calc_prefix();
	kmp();
	afisare();
	g.close();
	return 0;
}