Cod sursa(job #1228119)

Utilizator robertstrecheStreche Robert robertstreche Data 12 septembrie 2014 17:49:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <string.h>

#define lmax 2000005

using namespace std;

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

char c;
char N[lmax],M[lmax];

int n,m,k,nr;

int sol[lmax],prefix[lmax];

int main()
{

   while (f>>noskipws>>c && c!='\n')
     N[++n]=c;

   while (f>>noskipws>>c && c!='\n')
     M[++m]=c;

   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<=1000;i++)
      g<<sol[i]<<" ";

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