Cod sursa(job #2812986)

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

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

const int p = 31;
const int mod = 1e9 + 9;

const int maxN = 2e6 + 5;

long long pow[maxN];
long long h[maxN];
vector <int> ans;

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

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

    long long Hash = 0, pow = 1;
    for(int i = 0; i < s.size(); ++i) {
        Hash = (Hash * p + (s[i] - 'A'+1)) % mod;
        if(i != 0) pow = pow * p % mod;
    }
    long long subH = 0;
    for(int i = 0; i < t.size(); ++i) {
        if(i + 1 <= s.size()) {
            subH = (subH * p + (t[i]-'A'+1)) % mod;
        } else {
            subH = (subH - (pow * (t[i-s.size()]-'A'+1)) % mod + mod) % mod;
            subH = (subH * p + (t[i]-'A'+1)) % mod;
            if(subH == Hash) {
                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;
}