Cod sursa(job #2194909)

Utilizator adc98Adam Cristian adc98 Data 14 aprilie 2018 17:23:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define q 101
#define d 256

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

char s[2000001],p[2000001];

int poz[1001],nrElemente;

long long int hashs,pow;


long long int putere(long long int a,long  long int b)
{
    if(b==0) return 1;
      else if(b==1) return a % q;
            else if(b%2==0) return (putere(a,b/2) * putere(a,b/2)) % q;
                  else return (a * putere(a,b/2) * putere(a,b/2)) % q;
}

void calculHash(long long int poz)
{
    hashs= ( (hashs-s[poz]*pow)*d + s[poz+strlen(p)] ) % q;
    if(hashs<0) hashs+=q;
}

int main()
{
    fin.getline(p,2000001);
    fin.getline(s,2000001);

    int lg_p=strlen(p);
    int lg_s=strlen(s);

   if(lg_p > lg_s)
        {
         fout<<0;
         return 0;
        }

    long long int hashp=0;

    for(int i=0;i<lg_p;++i)
        {
         hashs=(hashs*d+s[i])%q;
         hashp=(hashp*d+p[i])%q;
        }

    pow=putere(d,lg_p-1);

    /*pow=1;
    for(int i=0;i<lg_p-1;++i)
        {
         pow=(pow*d)%q;
        }*/

    /*pow=1;
    for(int i=lg_p-1;i>=0;--i)
        {
         hashs=( hashs + ((int) (s[i]) * pow) % q) % q;
         hashp=( hashp + ((int) (p[i]) * pow) % q ) %q;
         if(i>0) pow=(pow * d) % q;
        }*/


    for(int i=0;i<=lg_s-lg_p;++i)
        {
         if(hashs==hashp)
            {
             int j=0;
             for(j=0;j<lg_p;++j)
                {
                 if(p[j]!=s[i+j]) break;
                }
             if(j==lg_p)
                {
                 if(nrElemente<1000) poz[nrElemente++]=i;
                  else nrElemente++;
                }
            }
         calculHash(i);
        }
    fout<<nrElemente<<"\n";
    if(nrElemente>1000) nrElemente=1000;
    for(int i=0;i<nrElemente;++i) fout<<poz[i]<<" ";
    return 0;
}