Cod sursa(job #1045632)

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