Cod sursa(job #1288208)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 8 decembrie 2014 18:00:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 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[1005];

int main()
{ int i,len,cuvlen;
    f.getline(s+1,2000003);
    f.getline(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;
           }
        }

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


    g<<nsol<<"\n";

     if (nsol>1000) nsol=1000;

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

    return 0;
}