Cod sursa(job #1586880)

Utilizator RadduFMI Dinu Radu Raddu Data 1 februarie 2016 18:19:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
 char s1[2000005],s2[2000005];
 int len1,len2,pi[2000005],sol[1005],nsol;

 void Prefix()
 { int i,k=0;
     for(i=2;i<=len1;i++)
     {
       while(s1[k+1]!=s1[i] && k)
        k=pi[k];

       if (s1[k+1]==s1[i]) k++;

       pi[i]=k;
     }
 }

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

   for(i=1;i<=len2;i++)
   {
     while(s1[k+1]!=s2[i] && k)
      k=pi[k];

     if (s1[k+1]==s2[i]) k++;

    if (k==len1)
    { nsol++;
      if (nsol<=1000) sol[nsol]=i-k+1;
    }

   }
 }
int main()
{ int i;
    f>>s1+1>>s2+1;
    len1=strlen(s1+1);
    len2=strlen(s2+1);
    Prefix();
    KMP();
    g<<nsol<<"\n";
    for(i=1;i<=nsol;i++)
      g<<sol[i]-1<<" ";
    return 0;
}