Cod sursa(job #298967)

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

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

void cit()
{
 scanf("%s\n",&x);
 strcpy(s2+1,x);
 scanf("%s",&x);
 strcpy(s1+1,x);
}

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<=Y[0];i++)
  printf("%d ",Y[i]);
}

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