Cod sursa(job #2750705)

Utilizator gasparrobert95Gaspar Robert Andrei gasparrobert95 Data 12 mai 2021 21:15:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 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, pw2 = 1, orig, orig2, cur, cur2, 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 * 62 % MOD, pw2 = pw2 * 62 % P;
    for (int i = 0; i < n; ++i) {
        orig = (orig * 62 + cod[a[i]]) % MOD;
        orig2 = (orig2 * 62 + cod[a[i]]) % P;
        cur = (cur * 62 + cod[b[i]]) % MOD;
        cur2 = (cur2 * 62 + cod[b[i]]) % P;
    }
    if (orig == cur && cur2 == orig2)
        pos.push_back(0);
    for (int i = n; i < b.size(); ++i) {
        cur = ((cur - cod[b[i - n]] * pw % MOD + MOD) * 62 + cod[b[i]]) % MOD;
        cur2 = ((cur2 - cod[b[i - n]] * pw2 % P + P) * 62 + cod[b[i]]) % P;
        if (cur == orig && cur2 == orig2 && 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;
}