Cod sursa(job #516840)

Utilizator acelasi7Tudor Maxim acelasi7 Data 26 decembrie 2010 18:09:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<stdio.h>
#include<string>
using namespace std;
#define niur 2000005
FILE *in=fopen("strmatch.in","r"),*out=fopen("strmatch.out","w");
char A[niur],B[niur];
int V[niur],la,lb,countt,AFI[1005];
void pre()
{
	int i,k=0;
	la=strlen(A);
	for(i=2;i<la;++i)
	{
		while(k&&A[i]!=A[k+1])
			k=V[k];
		if(A[k+1]==A[i])
			++k;
		V[i]=k;
	}
}
void kmp()
{
	int i,k=0;
	lb=strlen(B);
	for(i=1;i<lb;++i)
	{
		while(k&&A[k+1]!=B[i])
			k=V[k];
		if(A[k+1]==B[i])
			++k;
		if(k==la-1)
		{
			++countt;
			if(countt<1001) AFI[countt]=i-la+1;
		}
	}
}
int main()
{
	int i;
	A[0]=B[0]=2;
	fscanf(in,"%s",&A[1]);
	fscanf(in,"%s",&B[1]);
	pre();
	kmp();
	fprintf(out,"%d\n",countt);
	for(i=1;i<=countt;++i)
		fprintf(out,"%d ",AFI[i]);
	return 0;
}