Cod sursa(job #2237966)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 4 septembrie 2018 01:41:24
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <bits/stdc++.h>

using namespace std;

// String Hasher
template <int B, int MOD>
struct Hasher {
    // Static hash function
    template <typename iter_type>
    static int hash(iter_type begin, iter_type end) {
        int h = 0;
        for (iter_type it = begin; it != end; ++it)
            h = (1LL * h * B + *it) % MOD;
        return h;
    }
    // Data members
    vector <int> pows, h;
    // Constructor
    template <typename iter_type>
    Hasher(iter_type begin, iter_type end) {
        const int sz = end - begin + 1;
        pows.resize(sz), h.resize(sz);
        pows[0] = 1, h[0] = 0;
        for (iter_type it = begin; it != end; ++it) {
            pows[it - begin + 1] = (1LL * pows[it - begin] * B) % MOD;
            h[it - begin + 1] = (1LL * h[it - begin] * B + (*it)) % MOD;
        }
    }
    // Continuous subsequence hash query[l, r]
    int hash(int l, int r) {
        int res = (h[r + 1] - 1LL * h[l] * pows[r - l + 1]) % MOD;
        if (res < 0)
            res += MOD;
        return res;
    }
};

typedef Hasher <263, 1000000000 + 7> H1;
//typedef Hasher <277, 1000000000 + 9> H2;

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

    string pattern, str;
    cin >> pattern >> str;

    int h_pat1 = H1 :: hash(pattern.begin(), pattern.end());
    //int h_pat2 = H2 :: hash(pattern.begin(), pattern.end());
    H1 h1(str.begin(), str.end());
    //H2 h2(str.begin(), str.end());

    vector <int> ans;
    for (int i = 0; i + pattern.size() - 1 < str.size(); ++ i)
        if (h1.hash(i, i + pattern.size() - 1) == h_pat1)// && h2.hash(i, i + pattern.size() - 1) == h_pat2)
            ans.push_back(i);

    cout << ans.size() << '\n';
    if (ans.size() > 1000)
        ans.resize(1000);
    for (int i = 0; i < ans.size(); ++ i)
        cout << ans[i] << " \n"[i + 1 == ans.size()];
    return 0;
}