Cod sursa(job #2191120)

Utilizator adc98Adam Cristian adc98 Data 1 aprilie 2018 18:34:59
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define q 100007
#define d 26

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

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

long long int putere(long long int a,long  long 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);
    }

void calculHash(long long int x)
    {
     if(h)
        {
         //h-= ((int) (s[x-1]) * val) % q;
         h=( (h - (int) (s[x-1]) * val)* d + (int) (s[x+strlen(p)-1]) ) % q;
         //return h;
        }
    }

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

   if(strlen(p)>strlen(s))
        {
         fout<<0;
         return 0;
        }

    long long int pow=1,hashp=0;
    for(int i=strlen(p)-1;i>=0;--i)
        {
         h+=((int) (s[i]) * pow) % q;
         hashp+=((int) (p[i]) * pow) % q;
         pow*=d;
        }
    int contor=0;
    val=putere(d,strlen(p)-1);
    for(int i=0;i<=strlen(s)-strlen(p);++i)
        {
         if(h==hashp)
            {
             bool gasit=true;
             for(int j=0;j<strlen(p);++j)
                {
                 if(p[j]!=s[i+j])
                    {
                     gasit=false;
                     break;
                    }
                }
             if(gasit)
                {
                 contor++;
                 poz[nrElemente++]=i;
                }
            }
         calculHash(i+1);
        }
    fout<<contor<<"\n";
    for(int i=0;i<nrElemente;++i) fout<<poz[i]<<" ";
    return 0;
}