Cod sursa(job #309450)

Utilizator irene_mFMI Irina Iancu irene_m Data 30 aprilie 2009 12:36:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream.h>
#include <string.h>
#define MaxN 2000005
#define MaxSol 1024

char A[MaxN],B[MaxN];
long n,m,pi[MaxN],nrsol,sol[MaxSol];

void cit()
{
	ifstream fin("strmatch.in");
	fin.get(A,MaxN,'\n');
	fin.get();
	fin.get(B,MaxN,'\n');
	fin.close();
	m=strlen(A);
	n=strlen(B);
}

void trans()
{
	int i;
	for(i=m;i>=1;i--)
		A[i]=A[i-1];
	A[0]=' ';
	for(i=n;i>=1;i--)
		B[i]=B[i-1];
	B[0]=' ';
}

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

void potrivire()
{
	int k=0,i;
	for(i=1;i<=n;i++)
	{
		while(k && A[k+1]!=B[i])
			k=pi[k];
		if(A[k+1]==B[i])
			k++;
		if(k==m)
		{
			k=pi[m];
			nrsol++;
			if(nrsol<=1000)
				sol[nrsol]=i-m;
		}
	}
}

void afis()
{
	int i;
	ofstream fout("strmatch.out");
	fout<<nrsol<<'\n';
	for(i=1;i<=nrsol;i++)
		fout<<sol[i]<<" ";
	fout.close();
}

int main()
{
	cit();
	trans();
	prefix();
	potrivire();
	afis();
	return 0;
}