Cod sursa(job #2008239)

Utilizator savigunFeleaga Dragos-George savigun Data 5 august 2017 20:53:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;

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

typedef unsigned long long ULL;

const int C = 3;
char a[2000005], b[2000005];
ULL ha, hb[2000005];
vector<int> sol;


ULL pow(ULL a, int n) {
    if (n == 0) return 1;
    if (n % 2 == 0) return pow(a * a, n / 2);
    return a * pow(a, n - 1);
}

ULL hash_string(char* s) {
    int n = strlen(s) - 1;
    ULL h = 0;
    for (int i = 0; i <= n; ++i) {
        h += s[i] * pow(C, i);
    }

    return h;
}

void preprocess() {
    int n = strlen(b) - 1;
    for (int i = n; i >= 0; --i) {
        hb[i] = b[i] * pow(C, 0) + hb[i + 1] * C;
    }
}

ULL get_hash(int l, int r) {
    return hb[l] - hb[r + 1] * pow(C, r - l + 1);
}

int main()
{

    in >> a;
    in >> b;

    preprocess();
    ha = hash_string(a);

    int n = strlen(b) - 1;
    int m = strlen(a);
    for (int i = 0; i <= n - m + 1; ++i) {
        ULL h = get_hash(i, i + m - 1);
        if (h == ha) sol.push_back(i);
    }

    int no = sol.size();
    out << no << "\n";
    for (int i = 0; i < min(no, 1000); ++i) {
        out << sol[i] << " ";
    }

    return 0;
}