Cod sursa(job #1075269)

Utilizator sateanuAldea Andrei sateanu Data 8 ianuarie 2014 19:53:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<stdio.h>
#include<cstring>
using namespace std;

#define LMAX 2000001

char A[LMAX],B[LMAX];
int lenghtA,lenghtB,pre[LMAX],sol[LMAX],nr;

void prefix()
{
	int k,i;
	k=0;

	pre[1]=0;

	for(i=2;i<=lenghtA;i++)
	{
		while(k>0 && A[k+1]!=A[i])
			k=pre[k];

		if(A[k+1]==A[i])
			k++;

		pre[i]=k;
	}
}

void KMP()
{
	int k=0;

	for(int i=1;i<=lenghtB;i++)
	{
		while(k>0 && A[k+1]!=B[i])
			k=pre[k];

		if(A[k+1]==B[i])
			k++;

		if(k==lenghtA)
		{
			sol[++nr]=i-k;
			k=pre[k];
		}

	}
}

int main()
{
	FILE *f,*g;
	f=fopen("strmatch.in","r");
	g=fopen("strmatch.out","w");


	
	fgets(A,LMAX,f);
	fgets(B,LMAX,f);
	lenghtA=strlen(A)-1;
	lenghtB=strlen(B)-1;
	for(int i=lenghtA;i>0;i--)
		A[i]=A[i-1];
	A[0]=' ';

	for(int i=lenghtB;i>1;i--)
		B[i]=B[i-1];
	B[0]=' ';


	prefix();

	KMP();

	/*
	printf("A=%s\n", A);
	printf("B=%s\n", B);
	printf("%d\n", lenghtA);
	printf("%d\n", lenghtB);

	for(int i=1;i<=lenghtA;i++)
		printf("%d ",pre[i]);
	*/

	fprintf(g,"%d\n",nr);
	if(nr>1000)
		nr=1000;
	for(int i=1;i<=nr;i++)
		fprintf(g, "%d ",sol[i]);

	fclose(f);
	fclose(g);

	return 0;
}