Cod sursa(job #267694)

Utilizator FlorianFlorian Marcu Florian Data 27 februarie 2009 21:23:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#include<string.h>
#define Nmax 2000002
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
char A[Nmax], B[Nmax];
int n, m;
int pi[Nmax];
void read()
 {
  fscanf(f,"%s\n%s",A,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()
 {
  pi[1]=0;
  int i,k;
  k=0;
  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;
   }
 }
int s[1024];
void kmp()
 {
  int sol=0,i,q=0;
  for(i=1;i<=m;++i)
   {
    while(q && A[q+1] != B[i]) q=pi[q];
    if(A[q+1] == B[i]) ++q;
    if(q==n)
     {
      ++sol;
      if(sol<=1000) s[sol] = i-n;
      q=pi[n];
     }
   }
  fprintf(g,"%d\n",sol);
  if(sol>1000) sol=1000;
  for(i=1;i<=sol;++i) fprintf(g,"%d ",s[i]);
 }
int main()
 {
  read();
  prefix();
  kmp();
  return 0;
 }