Cod sursa(job #298994)

Utilizator andytrAlexandru Traista andytr Data 6 aprilie 2009 15:19:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#include <string.h>
#define Nmax 2000001

char s1[Nmax],s2[Nmax],x[Nmax];
int pi[Nmax],Y[1001];

void cit()
{
 fgets(s2+1,Nmax,stdin);
 if(s2[strlen(s2+1)]=='\n')
  s2[strlen(s2+1)]=NULL;
 fgets(s1+1,Nmax,stdin);
  if(s1[strlen(s1+1)]=='\n')
  s1[strlen(s1+1)]=NULL;
}

int min(int a,int b)
{
 return a<b?a:b;
}

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

void kmp()
{
 int m=strlen(s1+1),n=strlen(s2+1),q,i;
 prefix();
 q=0;
 for(i=1;i<=m;i++)
  {
   while(q>0&&s2[q+1]!=s1[i])
    q=pi[q];
   if(s2[q+1]==s1[i])
    q++;
   if(q==n)
    Y[++Y[0]]=i-n+1;
    //printf("%d ",i-n+1);
  }

}

void scr()
{
 int i;
 printf("%d\n",Y[0]);
 for(i=1;i<=min(Y[0],1000);i++)
  printf("%d ",Y[i]);
}

int main()
{
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 cit();
 kmp();
 scr();
 return 0;
}