Cod sursa(job #1576227)

Utilizator robertstrecheStreche Robert robertstreche Data 22 ianuarie 2016 11:06:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <cstring>
#include <vector>

#define LMAX 2000005

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

vector <int>sol;

int phi[LMAX];
char A[LMAX],B[LMAX];

int main()
{
   f>>(A+1)>>(B+1);

   int k=0,nr=0;
   int lA=strlen(A+1);
   int lB=strlen(B+1);

   for (int i=2;i<=lA;i++){
     while (k && A[i]!=A[k+1])k=phi[k];
     if (A[i]==A[k+1])k++;

     phi[i]=k;
   }

   k=0;
   for (int i=1;i<=lB;i++)
   {
     while (k && B[i]!=A[k+1])k=phi[k];
     if (B[i]==A[k+1])k++;

     if (k==lA && ++nr<1000)sol.push_back(i-lA);
   }

   g<<nr<<'\n';
   for (auto it:sol)g<<it<<" ";

   f.close();
   g.close();
}