Cod sursa(job #1928934)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 16 martie 2017 21:44:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <cstring>
#define LMAX 2000005

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int sufpre[LMAX];
char s1[LMAX];
char s2[LMAX];
int lg1;
int lg2;

int sol;
int psol[1005];

void citire();
void KMP();
void afisare();
void sufixe_prefixe();

int main()
{
citire();
KMP();
afisare();
fin.close();
fout.close();
return 0;
}

void citire()
    {
     fin>>s1;
     fin>>s2;
     lg1=strlen(s1);
     lg2=strlen(s2);
    }

void sufixe_prefixe()
    {
     int i;
     int index=0;
     for (i=1;i<lg1;)
         if (s1[i]==s1[index])
             {
              sufpre[i]=index+1;
              index++;
              i++;
             }
             else
             if (sufpre[index]!=0)
                 index=sufpre[index]-1;
                 else sufpre[i]=0, i++;
    }

void KMP()
    {
     int i;
     int j;
     sufixe_prefixe();
     for (i=0, j=0; i<lg2; )
          if (s1[j]==s2[i])
              {
               i++;
               j++;
               if (j==lg1)
                  {
                   sol++;
                   if (sol<=1000)
                      psol[sol]=i-lg1;
                   j=sufpre[j-1];
                  }
              }
              else if (j!=0)
                    j=sufpre[j-1];
                    else {
                     i++;
                    }
    }

void afisare()
    {
     int i;
     fout<<sol<<'\n';
     if (sol>1000)
         sol=1000;
     for (i=1;i<=sol;i++)
          fout<<psol[i]<<' ';
     fout<<'\n';
    }