Cod sursa(job #3226919)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 23 aprilie 2024 12:01:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e6;
const unsigned BASE = 37;

string a, b;

unsigned code(char c) {
    if (c == '#')
        return 53;
    if (c == '%')
        return 54;
    if (c >= 'A' && c <= 'Z')
        return c - 'A' + 1;
    return 27 + c - 'a';
}

unsigned pref[2 * NMAX + 2];
unsigned pBase[NMAX + 2];

unsigned get_hash(int st, int dr) {
    return pref[dr] - pref[st - 1] * pBase[dr - st + 1];
}

void solve() {
    fin >> a >> b;
    int sz = a.length();
    a = "%" + a + "#" + b;

    int ans = 0;
    vector<int> pos;

    pBase[0] = 1;
    for (int i = 1; i <= sz; i++)
        pBase[i] = pBase[i - 1] * BASE;

    for (int i = 1; i < a.length(); i++) {
        pref[i] = pref[i - 1] * BASE + code(a[i]);
    }

    unsigned firstHash = get_hash(1, sz);

    for (int i = 2; i + sz - 1 < a.length(); i++) {
        if (get_hash(i, i + sz - 1) == firstHash) {
            ans++;
            if (ans <= 1000)
                pos.push_back(i - sz - 2);
        }
    }

    fout << ans << '\n';
    for (int & x : pos)
        fout << x << ' ';
}

signed main() {
    solve();
    return 0;
}