Cod sursa(job #305233)

Utilizator cosserBula Ionut cosser Data 16 aprilie 2009 18:44:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb

#include<fstream>
 #include<vector>
#include<string>
 using namespace std;
 ifstream in("strmatch.in");
ofstream out("strmatch.out");
 char a[2000007], b[2000007];

 int i,j,m[2000010],nrsol;
 vector<int> sol;

 void kmppre()
 {
     i=0;
     j=-1;
     m[i]=j;
     int l2=strlen(a);
     while(i<=l2)
     {
         while(j>=0 && a[i]!=a[j])
             j=m[j];
        ++i;
         ++j;
         m[i]=j;
     }
 }

 void kmpmain()
 {
     int l1=strlen(b);
     int l2=strlen(a);
     i=0;
     j=0;
     while(i+j<=l1)
         {
             if(b[i+j]==a[j])
                 {
                     ++j;
                     if(j==l2)
                     {
                         ++nrsol;
                         if(nrsol<=1000)
                             sol.push_back(i);

                    }
                }
             else{
                 i=i+j-m[j];
                 if(j>0)
                     j=m[j];
                 }
         }
 }

 int main ()
 {

     in.get(a, 2000003);
    in.get();
     in.get(b, 2000003);
     kmppre();
     kmpmain();
     out<<nrsol<<"\n";
     if(!sol.empty())
     for(i=0;i<sol.size();i++)
         out<<sol[i]<<" ";

     return 0;
 }