Cod sursa(job #307239)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 23 aprilie 2009 18:38:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream>
#include<cstring>
#define MaxL 2000005
#define Min(a,b) ((a<b)?a:b)

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char A[MaxL],B[MaxL];
int N,M,i,phi[MaxL],pos[1005],n;

void prefix()
{	int i,q=0;
	for(i=2,phi[1]=0;i<=M;i++)
	{	while(q&&A[q+1]!=A[i])
			q=phi[q];
		if(A[q+1]==A[i]) q++;
		phi[i]=q;
	}
}
	
void KMP()
{	int i,q=0;
	for(i=1;i<=N;i++)
	{	while(q&&A[q+1]!=B[i])
			q=phi[q];
		if(A[q+1]==B[i])
			q++;
		if(q==M)
		{	q=phi[M];
			n++;
			if(n<=1000)
				pos[n]=i-M;
		}
	}
}

void print()
{	fout<<n<<'\n';
	for(i=1;i<=Min(n,1000);i++)
		fout<<pos[i]<<' ';
}

int main()
{	fin.getline(A,MaxL);
	fin.getline(B,MaxL);
	N=strlen(B);
	M=strlen(A);
	for(i=M+1;i>0;--i)
		A[i]=A[i-1];
	A[0]=' ';
	for(i=N+1;i>0;--i)
		B[i]=B[i-1];
	B[0]=' ';
	prefix();
	KMP();
	print();
	return 0;
}