Cod sursa(job #2813010)

Utilizator florinrafiliuRafiliu Florin florinrafiliu Data 5 decembrie 2021 17:03:27
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int p = 37;
const int mod1 = 1e9 + 9;
const int mod2 = 1e9 + 7;

vector <int> ans;

int main() {
    string s; fin >> s;
    string t; fin >> t;

    if(s.size() > t.size()) { fout << '0'; return 0;}

    int pow1 = 1, pow2 = 1;
    int H1 = 0, H2 = 0, h1 = 0, h2 = 0;

    for(int i = 0; i < s.size(); ++i) {
        H1 = (1ll * H1 * p + s[i]) % mod1;
        H2 = (1ll * H2 * p + s[i]) % mod2;

        h1 = (1ll * h1 * p + t[i]) % mod1;
        h2 = (1ll * h2 * p + t[i]) % mod2;

        if(i != 0) pow1 = (1ll * pow1 * p) % mod1;
        if(i != 0) pow2 = (1ll * pow2 * p) % mod2;
    }
    if(h1 == H1 && h2 == H2) {
        ans.push_back(0);
    }
    for(int i = s.size(); i < t.size(); ++i) {
        h1 = ((1ll * h1 - (pow1 * t[i-s.size()] % mod1) + mod1) % mod1 * p + t[i]) % mod1;
        h2 = ((1ll * h2 - (pow2 * t[i-s.size()] % mod2) + mod2) % mod2 * p + t[i]) % mod2;
        if(h1 == H1 && h2 == H2) {
            if(ans.size() < 1000)
                ans.push_back(i);
            else i = t.size();
        }
    }

    fout << ans.size() << '\n';
    for(int i : ans)
        fout << i - s.size() + 1 << " ";

    return 0;
}