Cod sursa(job #1364547)

Utilizator AnduRazvanMindrescu Andu AnduRazvan Data 27 februarie 2015 18:32:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir1[2000002],sir2[2000002];
int pi[2000002];
void Prelucrare(char t[2000002],int pi[2000002])
{ int i,m=strlen(t);int k;
pi[0]=0;k=0;
 for(i=1;i<=m;i++)
 { if(t[i]==t[k]) k++;
    else  {while(k>0&&t[k]!=t[i]) k=pi[k-1];
           if(t[k]==t[i]) k++;
          }
     pi[i]=k;
 }

}
int z,poz[2000002];
void KMP(char s[2000002],char t[2000002])
{ int n=strlen(s),i,k=0,m=strlen(t);
  for(i=0;i<n;i++)
   { if(s[i]==t[k]) k++;
    else { while(k>0&&t[k]!=s[i]) k=pi[k-1];
           if(t[k]==s[i]) k++;
         }
    if(k==m) {z++;poz[z]=i-m+1;}
   }
}
int main()
{  fin.get(sir1,2000002);fin.get();
   fin.get(sir2,2000002);
   Prelucrare(sir1,pi);
   KMP(sir2,sir1);
   fout<<z<<"\n";
   int i;
   if(z>=1000)
    for(i=1;i<=1000;i++)
        fout<<poz[i]<<" ";
   else for(i=1;i<=z;i++)
        fout<<poz[i]<<" ";
    return 0;
}