Cod sursa(job #1228094)

Utilizator robertstrecheStreche Robert robertstreche Data 12 septembrie 2014 17:10:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <string.h>

#define lmax 2000005

using namespace std;

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

char N[lmax],M[lmax];

int n,m,k,nr;

int sol[lmax],prefix[lmax];

int main()
{
   f>>N+1>>M+1;

   N[0]=M[0]='a';

   n=strlen(N)-1;
   m=strlen(M)-1;

   for (int i=2;i<=n;i++)
    {
        while (k>0 && N[k+1]!=N[i])
         k=prefix[k];

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

        prefix[i]=k;
    }

    k=0;

    for (int i=1;i<=m;i++)
     {
         while (k>0 && N[k+1]!=M[i])
         k=prefix[k];

         if (N[k+1]==M[i])
           k++;

        if (k==n)
         sol[++nr]=i-n;
     }

     g<<nr<<'\n';

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

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