Cod sursa(job #1288177)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 8 decembrie 2014 17:47:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
 char s[4000005],s2[2000005];
  int z[4000005],l,r,kp,a,nsol,sol[2000005];
int main()
{ int i,len,cuvlen;
    f.get(s+1,2000003); f.get();
    f.get(s2,2000003);
      cuvlen=strlen(s+1);


    strcat(s+1,s2);

    len=strlen(s+1);
    l=0; r=0;

    for(i=2;i<=len;i++)
    {
      if (i>r)
        {
           while(s[z[i]+1]==s[i+z[i]])
            z[i]++;

           l=i; r=l+z[i]-1;
        }
      else
        {
          kp=i-l+1; a=r-l+1;

          if (kp+z[kp]-1<a) z[i]=z[kp];
           else
           {
             z[i]=a-kp+1;

            while(s[z[i]+1]==s[i+z[i]])
             z[i]++;

           }
        }
       if (i>cuvlen && z[i]>=cuvlen) {nsol++; sol[nsol]=i-cuvlen-1;}
    }


    g<<nsol<<"\n";
    for(i=1;i<=nsol;i++)
     g<<sol[i]<<" ";

    return 0;
}