Cod sursa(job #1264958)

Utilizator BLz0rDospra Cristian BLz0r Data 16 noiembrie 2014 15:17:07
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <cstring>
using namespace std;

#define lgmax 2000002

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

char a[lgmax],b[lgmax];
int pi[lgmax],sl[1001],sol;

void prefix (char s[],int lg){
	int k=0;
	
	for (int i=2;i<=lg;++i){
		while (k>0 && s[i]!=s[k+1]) k=pi[k];
		if (pi[i]==pi[k+1]) k++;
		pi[i]=k;
	}
}

void match (char a[],char b[],int lga,int lgb){
	// lga<lgb
	int k=0;
	for (int i=1;i<=lgb;++i){
		while (k>0 && a[k+1]!=b[i]) k=pi[k];
		if (a[k+1]==b[i]) k++;
		if (k==lga){
			sl[++sol]=i-k;
			if (sol==1000) return;
		}
	}
}

int main(){
	int lga,lgb;
	
	fscanf (f,"%s%*c",a+1);
	fscanf (f,"%s",b+1);
	
	lga=strlen(a+1);
	lgb=strlen(b+1);
	
	prefix(a,lga);
	match (a,b,lga,lgb);
	
	fprintf (g,"%d\n",sol);
	for (int i=1;i<=sol;++i) fprintf (g,"%d ",sl[i]);
	
	return 0;
}