Cod sursa(job #1045595)

Utilizator NitaMihaitavoidcube NitaMihaita Data 1 decembrie 2013 19:35:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream>
#define numaru 2000000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int q[numaru],la,r,rr[numaru];
char a[numaru],b[numaru];
void F()
{
	int k=0,i;
	q[0]=0;
	for(i=1;a[i]!='\0';++i)
	{
		while(k>0 && a[k]!=a[i])k=q[k-1];
		if(a[k]==a[i])++k;
		q[i]=k;
	}
	la=i;
}
void strmatch()
{
	int k=0,i;
	for(i=0;b[i]!='\0';++i)
	{
		while(k>0 && a[k]!=b[i])k=q[k-1];
		if(a[k]==b[i])++k;
		if(k==la){ rr[r++]=i-la+1; k=q[k-1]; }
	}
}
int main()
{
	f>>a>>b;
	F();
	strmatch();
	r=(r<1000)?r:1000;
	g<<r<<"\n";
	for(int i=0;i<r;++i) g<<rr[i]<<" ";
	g<<"\n";
	f.close();
	g.close();
	return 0;
}