Cod sursa(job #2916964)

Utilizator florinrafiliuRafiliu Florin florinrafiliu Data 2 august 2022 15:25:42
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#define int long long
using namespace std;

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

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

vector <int> ans;

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

    int P1 = 1, P2 = 1;
    for(int i = 1; i < t.size(); ++i) {
        P1 = P1 * p % mod1;
        P2 = P2 * p % mod2;
    }

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

    int hash1 = 0, hash2 = 0;
    for(int i = 0; i < s.size(); ++i)
    {
        if(i >= t.size()) {
            hash1 = (hash1 - P1 * (s[i-t.size()] + 1) % mod1 + mod1) % mod1;
            hash2 = (hash2 - P2 * (s[i-t.size()] + 1) % mod2 + mod2) % mod2;
        }
        hash1 = (hash1 * p % mod1 + (s[i] + 1)) % mod1;
        hash2 = (hash2 * p % mod2 + (s[i] + 1)) % mod2;

        if(H1 == hash1 && H2 == hash2)
            ans.push_back(i - t.size() + 1);

        //cout << hash1 << " " << hash2 << " --> " << H1 << " " << H2 << '\n';
    }

    fout << ans.size() << "\n";

    for(int i = 0; i < min((int)ans.size(), (int)1000); ++i)
        fout << ans[i] << " ";

    return 0;
}