Cod sursa(job #2189553)

Utilizator adc98Adam Cristian adc98 Data 28 martie 2018 16:39:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <cstring>

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

char s[2000001],p[2000001];
int poz[1001],nrElemente;
int h,val;

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

int calculHash(int x)
    {
     if(h)
        {
         h-= (int) (s[x-1]) * val;
         h=h*37+ (int) (s[x+strlen(p)-1]);
         return h;
        }
    }

int main()
{
    fin.getline(p,2000001);
    fin.getline(s,2000001);
    int pow=1,hashp=0;
    for(int i=strlen(p)-1;i>=0;--i)
        {
         h+=(int) (s[i]) * pow;
         hashp+=(int) (p[i]) * pow;
         pow*=37;
        }
    int contor=0;
    if(h==hashp)
        {
         contor++;
         poz[nrElemente++]=0;
        }
    val=putere(37,strlen(p)-1);
    for(int i=1;i<strlen(s);++i)
        {
         int aux=calculHash(i);
         if(aux==hashp)
            {
             contor++;
             poz[nrElemente++]=i;
            }
        }
    fout<<contor<<"\n";
    for(int i=0;i<nrElemente;++i) fout<<poz[i]<<" ";
    return 0;
}