Cod sursa(job #302717)

Utilizator zbarniZajzon Barna zbarni Data 9 aprilie 2009 10:42:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<fstream.h>
#include<string.h>
#define nx 2000005
char A[nx],B[nx];
int pi[nx],poz[1005],n,m;

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