Cod sursa(job #1125117)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 26 februarie 2014 15:46:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
 int n,m,p[1005],v[2000005],ap;
 char a[2000005],b[1005];

 void Prefix()
 { int k=0,i;

  for(i=1;i<n;i++)
  {
    while(k>0 && a[k]!=a[i])
     k=p[k-1];

    if (a[k]==a[i])
     {k++; p[i]=k;}
  }

 }

int main()
{ int i,k;
    f.getline(a,2000003);
    f.getline(b,2000003);
     n=strlen(a);
     m=strlen(b);

    Prefix();

   k=0;
  for(i=0;i<m;i++)
  {
    while(k>0 && a[k]!=b[i])
     k=p[k-1];

    if (a[k]==b[i])
     k++;

    if (k==n) { ap++; v[ap]=i-n+1; }
  }

    g<<ap<<"\n";
   for(i=1;i<=ap;i++)
    g<<v[i]<<" ";

  return 0;
}