Cod sursa(job #2955523)

Utilizator gasparrobert95Gaspar Robert Andrei gasparrobert95 Data 17 decembrie 2022 12:03:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
#define baza 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
ll hasha, hashb, p = 1, dim, rez[1005];

int main() {
    fin >> a >> b;
    if (b.size() < a.size()) {
        fout << 0;
        return 0;
    }
    int l = a.size();
    for (int i = 0; i < l; ++i) {
        hasha = (hasha * baza + a[i]) % MOD;
        if (i != 0)
            p = (p * baza) % MOD;
    }
    for (int i = 0; i < l; ++i)
        hashb = (hashb * baza + b[i]) % MOD;
    if (hasha == hashb)
        ++dim;
    for (int i = l; i < b.size(); ++i) {
        hashb = ((hashb - (b[i - l] * p) % MOD + MOD) * baza + b[i]) % MOD;
        if (hasha == hashb && dim < 1000)
            rez[++dim] = i - l + 1;
    }
    fout << dim << "\n";
    for (int i = 1; i <= dim; ++i)
        fout << rez[i] << " ";
    return 0;
}