Cod sursa(job #2412683)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 22 aprilie 2019 14:35:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

const int nmax = 2 * 1e6;
const int base = 75;

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

unsigned long long a[1 + nmax], b[1 + nmax];
string s1, s2;
unsigned long long maxexp;
vector <int> sol;

void citire() {
    in >> s1 >> s2;
}

void hasha() {
    maxexp = 1;
    for(int i = 0; i < s1.size(); i ++) {
        if(i == 0) {
            a[i] = (s1[i] - '0');
        } else {
            a[i] = a[i - 1] * base + (s1[i] - '0');
        }
        maxexp *= base;
    }
}

void hashb() {
    for(int i = 0; i < s2.size(); i ++) {
        if(i == 0) {
            b[i] = (s2[i] - '0');
        } else {
            b[i] = b[i - 1] * base + (s2[i] - '0');
        }
    }
}

void solve() {
    hasha();
    hashb();

    int nsol = 0, n = s1.size();
    for(int i = n - 1; i < s2.size(); i ++) {
        unsigned long long cur;
        if(i == n - 1) {
            cur = b[i];
        } else {
            cur = b[i] - b[i - n] * maxexp;
        }

        if(cur == a[n - 1]) {
            nsol ++;
            if(sol.size() < 1000) {
                sol.push_back(i + 1 - n);
            }
        }
    }

    out << nsol << '\n';
    for(int i = 0; i < sol.size(); i ++) {
        out << sol[i] << " ";
    }
}

int main() {

    citire();
    solve();

    return 0;
}