Cod sursa(job #597286)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 21 iunie 2011 17:20:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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;
		if(A[2]==A[1])
			j=1;
		else
			j=0;
		table[0]=-1;
		table[1]=0;
		for(i=2;i<la;i++){
			if( A[i] == A[j] && j!=0 ){
				table[i] = table[i-1]+1;
				j++;
			}
			else if ( A[i] == A[j] && j==0){
				table[i] = 0;
				j=1;
			}
			else if (j!=0){
				table[i] = table[i-1]+1;
				j=0;			
			}
			else{
				table[i] = 0;
				j = 0;
			}
		}
		
		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{
			for(;(m+i)<lb;){
				if(A[i]==B[m+i]){
					if(i==(la-1)){
						v[aparitii]=m;
						aparitii++;
						if(table[i]==0)
							m=m+la;
						else
							m=m+i-table[i];
						i=table[i];
					}
					else
						i++;
				}
				else{
					m=m+i-table[i];
					i = table[i];
					if(i==-1)
						i=0;
				}
			}
		}
		fprintf(fpw,"%d\n",aparitii);
		for(i=0;i<aparitii;i++)
			fprintf(fpw,"%d ",v[i]);
	}

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