Cod sursa(job #856675)

Utilizator taigi100Cazacu Robert taigi100 Data 16 ianuarie 2013 20:40:28
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#define Nm 2000005

#include <stdio.h>
#include <string.h>
#include <iostream>

int D[256];
char T[Nm],P[Nm];
int Tl,Pl;
int cont;
int v[1005];
void initialize_Lenght()
{
	Tl=strlen((char*)T);
	Pl=strlen((char*)P);
}
void compute_D()
{
	for(int i=0;i<256;i++)
		D[i]=Pl;
	for(int i=0;i<Pl;i++)
		D[P[i]]=Pl-i-1;
}
void Boyer_Moore()
{
	int i=Pl-1,j=Pl-1;
	
	while ( i<=Tl ) 
	{
		j=Pl-1;
		while(P[j]==T[i] && i>=0 && j>=0)
		{
			i--;
			j--;
		}
		if(j==-1)
		{
			cont++;
			if(cont<=1000)
				v[cont]=i+1;
			i+=Pl+1;
		}
		else
			i+=D[T[i]];
	}
}
int main()
{
	FILE *f=freopen("strmatch.in","r",stdin);
	FILE *g=freopen("strmatch.out","w",stdout);
    gets(P);
	gets(T);
	initialize_Lenght();
	compute_D();
	Boyer_Moore();
	printf("%d\n",cont);
	for(int i=1;i<=cont;i++)
	{
	   if(i>1000)
		   i=cont+10;
	   else
		   printf("%d ",v[i]);
	}
}