Cod sursa(job #2009428)

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

using namespace std;

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

unsigned long long sph[20001000];
unsigned long long put[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];
    }
    put[0] = 1;
    for (int i=1; i<=csize; i++){
        put[i] = put[i-1] * b;
    }
    for (int i=0; i<=csize; i++){
        hash = sph[i] - sph[i+gsize]*put[gsize];
        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;
}