Cod sursa(job #540999)

Utilizator giuliastefGiulia Stef giuliastef Data 24 februarie 2011 18:55:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
// Potrivirea sirurilor - KMP

#include <fstream>
#define LMAX 2000011
using namespace std;
char a[LMAX],b[LMAX];
int nr,poz[1001],pi[LMAX];
inline int minim(int a, int b)
{
       if(a<=b)
        return a;
       return b;
}
void make_prefix()
{
     int i,k,lg;
     lg=strlen(a)-1;
     pi[1]=0;
     k=0;
     for(i=2;i<=lg;i++)
     {
      while( k>0 && a[i]!=a[k+1])
       k=pi[k];
      if(a[i]==a[k+1])
       k=k+1;
      pi[i]=k;
     }
}
int main()
{
    int i,lga,lgb,q;
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>a>>b;
    lga=strlen(a);
    lgb=strlen(b);
    for(i=lga;i>0;i--) a[i]=a[i-1]; a[0]=' ';
    for(i=lgb;i>0;i--) b[i]=b[i-1]; b[0]=' ';
    
    make_prefix();
    
    q=0;
    for(i=1;i<=lgb;i++)
    {
     while(q && a[q+1]!=b[i])
      q=pi[q];
     if(a[q+1]==b[i])
      q=q+1;
     if(q==lga)
     {
      q=pi[lga];
      nr++;
      if(nr<=1000)
       poz[nr]=i-lga;
     }
    }
    g<<nr<<"\n";
    for(i=1;i<=minim(nr,1000);i++)
     g<<poz[i]<<" ";
    g<<"\n";
    return 0;
}