Cod sursa(job #2301561)

Utilizator tiberiu392Tiberiu Ungurianu tiberiu392 Data 13 decembrie 2018 09:49:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <cstring>
#define nmax 2000005

using namespace std;

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

int poz[1002];
int t[nmax];
char s[nmax];
char z[nmax];
int c , n, m;

void constr()
{
    int j = 0 ;
     for ( int i = 2 ; z[i] != NULL ; i ++ )
     {
         while(z[j+1]!=z[i]&&j)
            j=t[j];
         if(z[j+1]==z[i])
            j++;
         t[i]=j;
     }
}
void cauta()
{
    int j = 0 ;
    int m = strlen(z);
    for (int i = 1 ; s[i] != NULL ; i ++ )
    {
        while(z[j+1]!=s[i]&&j)
             j=t[j];
        if(z[j+1]==s[i])
            j++;
        if(j==m-1)
        {
            j=t[j];
            c++;
            if(c<=1000)
                poz[c]=i-m+1;
        }
    }
}
int main()
{
   f.getline(z,nmax);
   f.getline(s,nmax);
   int n = strlen(s);
   int m = strlen(z);
   for (int i = n ; i >= 1 ; i --)
      s[i]=s[i-1];
   for(int j = m ; j >= 1 ; j-- )
      z[j]=z[j-1];
   s[0]=' ';
   z[0]=' ';
   s[n+1]=NULL;
   z[m+1]=NULL;
   constr();
   cauta();
     g<< c <<'\n';
     for (int i = 1 ; i <= min(c,1000); i ++ )
        g <<poz[i]<<" " ;
    return 0;
}