Cod sursa(job #2009431)

Utilizator Alex18maiAlex Enache Alex18mai Data 9 august 2017 17:34:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <string>

using namespace std;

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

unsigned long long sph[20001000];
int pos[1005];

int main() {
    string gasit;
    string cautare;
    cin>>gasit;
    cin>>cautare;
    int cont = 0;
    int gsize = gasit.size();
    int csize = cautare.size();
    unsigned long long b='z' + 1;
    unsigned long long hgasit = 0;
    unsigned long long hash = 0;
    for (int i=gsize; i>=0; i--){
        hgasit *= b;
        hgasit += gasit[i];
    }
    for (int i=csize; i>=0; i--){
        sph[i] = sph[i+1]*b + cautare[i];
    }
    unsigned long long putgsize = 1;
    for (int i=1; i<=gsize; i++){
        putgsize = putgsize * b;
    }
    for (int i=0; i<=csize; i++){
        hash = sph[i] - sph[i+gsize]*putgsize;
        if (hash == hgasit){
            cont++;
            if (cont <= 1000){
                pos[cont] = i;
            }
        }
    }
    cout<<cont<<'\n';
    for (int i=1; i<= min(cont , 1000); i++){
        cout<<pos[i]<<" ";
    }
    return 0;
}