Cod sursa(job #278974)

Utilizator FlorianFlorian Marcu Florian Data 12 martie 2009 17:06:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<stdio.h>
#include<string.h>
#define Nmax 2000003
char A[Nmax], B[Nmax];
int sol[1005];
int nr=0;
int pi[Nmax],n,m;
void read()
 {
  freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);
  scanf("%s\n",A);
  scanf("%s\n",B);
  n=strlen(A);
  m=strlen(B);
  int i;
  for(i=n;i>0;--i) A[i]=A[i-1]; A[0]=' ';
  for(i=m;i>0;--i) B[i]=B[i-1]; B[0]=' ';
 }
void prefix()
 {
  int k=0;
  int i;
  pi[1]=0;
  for(i=2;i<=n;++i)
   {
    while(k && A[k+1] != A[i]) k=pi[k];
    if(A[k+1] == A[i]) ++k;
    pi[i]=k;
   }
 }
void kmp()
 {
  int k=0,i;
  for(i=1;i<=m;++i)
   {
    while(k && A[k+1] != B[i]) k=pi[k];
    if(A[k+1] == B[i]) ++k;
    if(k==n)
     {
      ++nr;
      if(nr<=1000) sol[nr]=i-n;
      k=pi[n];
     }
   }
  printf("%d\n",nr);
  if(nr>1000) nr=1000;
  for(i=1;i<=nr;++i) printf("%d ",sol[i]);
 }
int main()
 {
  read();
  prefix();
  kmp();
  return 0;
 }