Cod sursa(job #659241)

Utilizator maritimCristian Lambru maritim Data 10 ianuarie 2012 13:56:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>
#include<fstream>
using namespace std;

FILE *f = fopen("strmatch.in","r");
ofstream g("strmatch.out");

#define MaxN 2000100
#define Max1000 1010

int nr,Pi[MaxN],C[Max1000];
char A[MaxN],B[MaxN];

void Prefix(void)
{
	int k = -1;
	Pi[0] = -1;
	
	for(int i=1;A[i];i++)
	{
		for(;k > -1 && A[k+1] != A[i];k = Pi[k]);
		if(A[k+1] == A[i]) ++ k;
		Pi[i] = k;
	}
}

void KMP(void)
{
	int q = -1;
	
	for(int i=0;B[i];i++)
	{
		for(;q > -1 && A[q+1] != B[i];q = Pi[q]);
		if(A[q+1] == B[i]) ++q;
		if(A[q+1] == '\n')
		{
			if(C[0] < 1000)
				C[++C[0]] = i-q;
			++ nr;
			q = Pi[q];
		}
	}
}

int main()
{
	fgets(A,sizeof(A),f);
	fgets(B,sizeof(B),f);
	Prefix();
	KMP();
	
	g << nr << "\n";
	for(int i=1;i<=C[0];i++)
		g << C[i] << " ";
	
	return 0;
}