Cod sursa(job #1288196)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 8 decembrie 2014 17:56:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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]++;

             l=i; r=i+z[i]-1;
           }
        }
       // cout<<i<<" l="<<l<<" r="<<r<<" z="<<z[i]<<"\n";
       if (i>cuvlen && z[i]>=cuvlen) {nsol++; sol[nsol]=i-cuvlen-1;}
    }


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

    return 0;
}