Cod sursa(job #547968)

Utilizator irene_mFMI Irina Iancu irene_m Data 6 martie 2011 21:25:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>
#include <cstring>
#define MaxN 2000005
#define MaxM 1005
#define infile "strmatch.in"
#define outfile "strmatch.out"

char A[MaxN],B[MaxN];
int pi[MaxN],sol[MaxM],nrsol;

void read()
{
      int i,n;
      scanf("%s%s",&A,&B);
      n=strlen(A);
      for(i=n;i>0;i--)
            A[i]=A[i-1];
      n=strlen(B);
      for(i=n;i>0;i--)
            B[i]=B[i-1];

      A[0]=B[0]='0';
}

void prefix()
{
      int n=strlen(A)-1,k=0,i;
      for(i=2;i<=n;i++)
      {
            while(k>0 && A[k+1]!=A[i])
                  k=pi[k];
            if(A[k+1]==A[i])
                  k++;
            pi[i]=k;
      }
}

void match()
{
      int n=strlen(A)-1,m=strlen(B)-1,k=0,i;
      for(i=1;i<=m;i++)
      {
            while(k>0 && A[k+1]!=B[i])
                  k=pi[k];
            if(A[k+1]==B[i])
                  k++;
            if(k==n)
            {
                  nrsol++;
                  if(nrsol<=1000)
                        sol[nrsol]=i-n;
            }
      }
}

void write()
{
      int i;
      printf("%d\n",nrsol);
      if(nrsol>1000) nrsol=1000;
      for(i=1;i<=nrsol;i++)
            printf("%d ",sol[i]);
}

int main()
{
      freopen(infile,"r",stdin);
      freopen(outfile,"w",stdout);

      read();
      prefix();
      match();
      write();

      fclose(stdin);
      fclose(stdout);
      return 0;
}