Cod sursa(job #405782)

Utilizator lucianvnDragomir Lucian lucianvn Data 28 februarie 2010 19:05:52
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <string.h>
using namespace std;
#define MAX 2000010
char sir1[MAX],sir2[MAX];
long daubine[MAX],lungime1,lungime2,pozitii[1010],nr,q,i;
void prefix()
{
	q=0;
	daubine[1]=0;
	for(i=2;i<=lungime1;++i)
	{
		while(q && sir1[q+1]!=sir1[i])
			q=daubine[q];
		if(sir1[q+1]==sir1[i]) 
			++q;
		daubine[i]=q;                
	}
}
void kmp()
{
	nr=0;
	q=0;
	for(i=1;i<=lungime2;++i)
	{
		while(q && sir1[q+1]!=sir2[i]) 
			q=daubine[q];
		if(sir1[q+1]==sir2[i]) 
			++q;
		if(q==lungime1) 
		{
			++nr;
			if(nr<=1000) pozitii[nr]=i-lungime1;
			q=daubine[q];
		}                  
	}
}
int main()
{
  ifstream intrare("replace.in");
  intrare>>sir1+1;
  intrare>>sir2+1;
  intrare.close();
  sir1[0]=' ';
  sir2[0]=' ';
  lungime1=strlen(sir1)-1;
  lungime2=strlen(sir2)-1;
  prefix();
  kmp();
  ofstream iesire("replace.out");
  iesire<<nr<<"\n";
  for(i=1;(i<=nr && i<=1000);++i) 
	iesire<<pozitii[i]<<" ";
  iesire.close();
  return 0;    
}