Cod sursa(job #2750698)

Utilizator gasparrobert95Gaspar Robert Andrei gasparrobert95 Data 12 mai 2021 21:05:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
#define ll long long
#define MOD 9987671
#define P 9981121
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
ll nr, pw = 1, orig, cur, cod[130];
vector <ll> pos;

int main() {
    fin >> a >> b;
    for (int i = '0'; i <= '9'; ++i)
        cod[i] = ++nr;
    for (int i = 'a'; i <= 'z'; ++i)
        cod[i] = ++nr;
    for (int i = 'A'; i <= 'Z'; ++i)
        cod[i] = ++nr;
    ll n = a.size();
    for (int i = 1; i < n; ++i)
        pw = pw * 64 % MOD;
    for (int i = 0; i < n; ++i) {
        orig = orig * 64 % MOD + cod[a[i]] % MOD;
        cur = cur * 64 % MOD + cod[b[i]] % MOD;
    }
    if (orig == cur)
        pos.push_back(0);
    for (int i = n; i < b.size(); ++i) {
        cur = ((cur - cod[b[i - n]] * pw % MOD + MOD) * 64 + cod[b[i]]) % MOD;
        if (cur == orig && pos.size() < 1000)
            pos.push_back(i - n + 1);
    }
    fout << pos.size() << "\n";
    for (int i = 0; i < pos.size(); ++i)
        fout << pos[i] << " ";
    return 0;
}