Cod sursa(job #693857)

Utilizator noruIlies Norbert noru Data 27 februarie 2012 17:24:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<stdio.h>
#include<string.h>
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
char s[2000003],t[2000003];
int v[2000003],pi[2000003];
void verif(int &k)
{
	int q;
    q = 0;
	int r=0;
	int i;
	pi[strlen(s)]=1;
    for ( i = 1; i <= strlen(t); i++)
	{
      while (q > 0 && s[q+1] != t[i])
        q = pi[q];
      if (s[q+1] == t[i])
        q++;
      if (q == strlen(s)-1) {
        v[++k]=i-strlen(s)+1;
        q = pi[q];
		t[i-strlen(s)+2]='z'+1;
		i=i-strlen(s)+2;} 
	}
}
int main()
{
	int k=0,i;
	fscanf(f,"%s",&s);
	fscanf(f,"%s",&t);
	for (i=strlen(t);i>=0;i--)
		t[i+1]=t[i];
	for (i=strlen(s);i>=0;i--)
		s[i+1]=s[i];
	verif(k);
	fprintf(g,"%d\n",k);
	if (k>1000) k=1000;
	for (int i=1;i<=k;i++) fprintf(g,"%d ",v[i]);
	return 0;
}