Cod sursa(job #292477)

Utilizator zbarniZajzon Barna zbarni Data 31 martie 2009 10:51:22
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream.h>
#include<string.h>
#define nx 2000005
char A[nx],B[nx];
int n,m;
int pi[nx],pos[nx];
void make_prefix()
 {
  int i,k=0;
  for (i=2,pi[1]=0;i<=n;++i)
   {
    while (k && A[k+1]!=A[i])
	k=pi[k];
    if (A[k+1]==A[i])
      ++k;
    pi[i]=k;
   }
 }

int main()
 {
  int x=0,k=0,i;
  ifstream be ("strmatch.in");
  ofstream ki ("strmatch.out");
  be>>A>>B;
  be.close();
  n=strlen(A),m=strlen(B);
  for (i=n;i;--i)
    A[i]=A[i-1];
  A[0]=' ';
  for (i=m;i;--i)
    B[i]=B[i-1];
  B[0]=' ';
  make_prefix();
  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)
      {
       k=pi[n];
       ++x;
       if (x<=1000) pos[x]=i-n;
      }
   }
  ki<<x<<'\n';
  for (i=1;i<=x && i<=1000;++i)
    ki<<pos[i]<<' ';
  ki<<'\n';
  ki.close();
  return 0;
 }