Cod sursa(job #2812995)

Utilizator florinrafiliuRafiliu Florin florinrafiliu Data 5 decembrie 2021 16:47:38
Problema Potrivirea sirurilor Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const long long p = 37;
const long long mod1 = 1e9 + 9;
const long long 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;}

    long long Hash1 = 0, Hash2 = 0, pow1 = 1, pow2 = 1;
    long long subH1 = 0, subH2 = 0;
    for(int i = 0; i < s.size(); ++i) {
        Hash1 = (1ll * Hash1 * p + (s[i] - 'A'+1)) % mod1;
        Hash2 = (1ll *Hash2 * p + (s[i] - 'A'+1)) % mod2;

        subH1 = (1ll * subH1 * p + (t[i]-'A'+1)) % mod1;
        subH2 = (1ll * subH2 * p + (t[i]-'A'+1)) % mod2;

        if(i != 0) pow1 = pow1 * p % mod1;
        if(i != 0) pow2 = pow2 * p % mod2;
    }
    if(subH1 == Hash1 && subH2 == Hash2) {
        ans.push_back(1);
    }
    for(int i = s.size(); i < t.size(); ++i) {
        if(i + 1 <= s.size()) {
            subH1 = (subH1 * p + (t[i]-'A'+1)) % mod1;
            subH2 = (subH2 * p + (t[i]-'A'+1)) % mod2;

        } else {
            subH1 = (1ll * subH1 - (pow1 * (t[i-s.size()]-'A'+1)) % mod1 + mod1) % mod1;
            subH2 = (1ll * subH2 - (pow2 * (t[i-s.size()]-'A'+1)) % mod2 + mod2) % mod2;
            subH1 = (1ll * subH1 * p + (t[i]-'A'+1)) % mod1;
            subH2 = (1ll * subH2 * p + (t[i]-'A'+1)) % mod2;
            if(subH1 == Hash1 && subH2 == Hash2) {
                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;
}