Cod sursa(job #1997032)

Utilizator catalinlupCatalin Lupau catalinlup Data 3 iulie 2017 11:32:53
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
#define LMAX 2000000
#define NMAX 1000
#define base 101
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
//const int base=11;

char Cuvant[LMAX];
int CuvLen=0;
int HashCuv=0;
char String[LMAX];
int Hash=0;
int StringLen=0;
int Loc[NMAX];
int num=0;

int pow(int n,int e);

void Read(){
    in.getline(Cuvant,LMAX);
    CuvLen=strlen(Cuvant);
    in.getline(String,LMAX);
    StringLen=strlen(String);
    for(int i=0;i<CuvLen;i++){
        HashCuv+=pow(base,CuvLen-1-i)*int(Cuvant[i]);

    }

}

bool Egal(int seg){
    for(int i=0;i<CuvLen;i++){
        if(Cuvant[i]!=String[seg+i]){
            //cout<<Cuvant[i]<<String[seg+i]<<endl;
            return false;
        }
    }
    return true;
}

int pow(int n,int e){
    int r=1;
    for(int i=0;i<e;i++)
        r*=n;
    return r;
}

void RabinKarp(){
    Hash=0;
    for(int i=0;i<CuvLen;i++){
        int Num=pow(base,CuvLen-1-i);
        Hash=Hash+Num*int(String[i]);
    }

    for(int i=0;i<=StringLen-CuvLen;i++){
        if(Hash==HashCuv){
            if(Egal(i)){
                Loc[num++]=i;
                if(num>=NMAX-1)
                    break;
            }
        }
        Hash=base*(Hash-(double)String[i]*pow(base,CuvLen-1))+String[i+CuvLen];
    }
    out<<num<<"\n";
    for(int i=0;i<num;i++)
        out<<Loc[i]<<" ";
}




int main()
{
    Read();
    RabinKarp();
    return 0;
}