Cod sursa(job #144404)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 27 februarie 2008 16:15:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
#include<string.h>
char a[2000010],b[2000010];
long int la,lb,i,k,pr[2000010],sol,poz[1001];
int main()
{
	FILE *f,*g;f=fopen("strmatch.in","r");g=fopen("strmatch.out","w");
	fscanf(f,"%s",&a[1]);fscanf(f,"%s",&b[1]);
	la=strlen(&a[1]);lb=strlen(&b[1]);
	for(i=2;i<=la;i++)
	{ while(k>0&&a[k+1]!=a[i])k=pr[k];
	  if(a[k+1]==a[i])k++;
	  pr[i]=k;
	}
	k=0;
	for(i=1;i<=lb;i++)
	{ while(k>0&&a[k+1]!=b[i])k=pr[k];
	  if(a[k+1]==b[i])k++;
	  if(k==la)
	  { sol++;
	    if(sol<=1000)poz[sol]=i-la;
          }
	}
	fprintf(g,"%ld\n",sol);
	sol=(sol<1000)?sol:1000;
	for(i=1;i<=sol;i++)
	 fprintf(g,"%ld ",poz[i]);
	fcloseall();
	return 0;
}