Cod sursa(job #621458)

Utilizator noname15119Noname noname15119 Data 16 octombrie 2011 19:54:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<stdio.h>

#define minim(a,b) ((a<b)?a:b)
#define max 2000005

int M,N;
char A[max],B[max];
int pi[max],pos[1024];

void prefix(void)
{
  int q=0;
  pi[1]=0;
  for(int i=2;i<=M;i++)
   {
     while(q && A[q+1]!=A[i]) q=pi[q];
     if (A[q+1]==A[i]) q++;
     pi[i]=q;
   }
}

int main(void)
{
 int i,q=0,n=0;
 
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 fgets(A,sizeof(A),stdin);
 fgets(B,sizeof(B),stdin);
 
 for(;(A[M]>='A' && A[M]<='Z') || (A[M]>='a' && A[M]<='z') || (A[M]>='0' && A[M]<='9');++M);
 for(;(B[N]>='A'&& B[N]<='Z') || (B[N]>='a' && B[N]<='z') || (B[N]>='0' && B[N]<='9');++N);
 for(i=M;i;--i) A[i]=A[i-1]; A[0]=' ';
 for(i=N;i;--i) B[i]=B[i-1]; B[0]=' ';
 
 //sprintf("%d %d\n",M,N);
 prefix();

 for(i=1; i<=N;i++)
  {
   while(q && A[q+1]!=B[i]) q=pi[q];
   if (A[q+1]==B[i]) q++;
   if (q==M)
    {
     q=pi[M];
     n++;
     if (n<=1000) pos[n]=i-M;
    }
  }

  printf("%d\n",n);
  for(i=1;i<=minim(n,1000);i++)
    printf("%d ",pos[i]);
  printf("\n");

  return 0;
}