Cod sursa(job #267134)

Utilizator yoyolichIoana Ardeleanu yoyolich Data 26 februarie 2009 19:58:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<stdio.h>
#include<vector>
using namespace std;
#include<string.h>
#define nmax 2000010
FILE *f=fopen("strmatch.in","r"), *g=fopen("strmatch.out","w");

char a[nmax],b[nmax];
int urm[nmax],pos[1001],A,B,nr,i,k;

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

int main()
{
	fgets(a,nmax,f);
	fgets(b,nmax,f);
	A=strlen(a);A--;
	B=strlen(b);
	//fprintf(g,"%d ",B);
	prefix();
	
	k=-1;
	
	for(i=0;i<B;i++)
	{
		while(k>=0 && a[k+1]!=b[i]) k=urm[k];
		if(a[k+1]==b[i]) k++;
		if(k==A-1)
		{
			nr++;
			if(nr<=1000) pos[nr]=i-k;
		}
	}
	
	fprintf(g,"%d\n",nr);
	for(i=1;i<=min(1000,nr);i++) fprintf(g,"%d ",pos[i]);
	fclose(f);
	fclose(g);
	return 0;
}