Cod sursa(job #597660)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 22 iunie 2011 19:25:27
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <stdio.h>
#include <string.h>


int main(int argc, char* argv[])
{
	char *A;
	char *B;
	int *table;
	int la,lb;

	A = new char[2000000];
	B = new char[2000000];

	FILE *fpr,*fpw;
	fpr = fopen("strmatch.in","r");
	fpw = fopen("strmatch.out","w");

	fgets(A,2000000,fpr);
	fgets(B,2000000,fpr);
	la = strlen(A)-1;
	lb = strlen(B)-1;

	table = new int[la];

	if(la>lb)
		fprintf(fpw,"0");
	else if(la==lb)
	{
		if(strcmp(A,B)==0)
			fprintf(fpw,"1 \n0");
		else
			fprintf(fpw,"0");
	}
	else{
		int i;
		int j=0;
		table[0]=-1;
		table[1]=0;
		for(i=2;i<la;){
			if(A[i-1]==A[j]){
				table[i]=j;
				j++;
				i++;
			}
			else if(j!=0)
				j=table[j];
			else{
				table[i]=0;
				i++;
			}
		}
		
		int aparitii=0;
		int v[10000];
		int m=0;
		i=0;

		while( m<lb && A[0]!=B[m])
			m++;
		if(m==lb)
			aparitii=0;
		else{
			while((m+i)<lb){
				if(A[i]==B[m+i]){
					if(i==(la-1)){
						if(aparitii<1000)
							v[aparitii]=m;
						aparitii++;
						m=m+i-table[i];
						i=table[i];
					}
					i++;
				}
				else{
					m=m+i-table[i];
					if(table[i] > -1)
						i=table[i];
					else
						i=0;
				}
			}
		}
		fprintf(fpw,"%d\n",aparitii);
		if(aparitii>1000)
				aparitii=1000;
		for(i=0;i<aparitii;i++)
			fprintf(fpw,"%d ",v[i]);
	}

	fclose(fpr);
	fclose(fpw);
	delete table;
	delete A;
	delete B;
	return 0;
}