Cod sursa(job #2773337)

Utilizator PopaMihaimihai popa PopaMihai Data 6 septembrie 2021 16:43:48
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("strmatch.in"); ofstream fout("strmatch.out");
const int base = 71, mod = 1e9 + 7;

string a, b;
int A, B, masca = 1, i, e, ans[1005], sz;

int main()
{
    fin >> a;
    fin >> b;

    sz = a.size();

    for(i = 0; i < sz; i++){

        A = (1LL * A * base + a[i] - '0' + 1) % mod;
        B = (1LL * B * base + b[i] - '0' + 1) % mod;
    }
    for(int i = 1; i < sz; i++)
        masca = (1LL * masca * base) % mod;

    while(i < b.size())
    {
        int bct, btest;
        bct = b[i - sz] - '0' + 1;
        btest = b[i + 1] - '0' + 1;
        if(A == B){
            e++;
            if(e <= 1000)
                ans[e] = i - sz;
        }
        B = (B - (1LL * bct * masca % mod) + mod) % mod; /// elimin prima litera
        B = (1LL * B * base % mod + b[i] - '0' + 1) % mod; /// adaug urmatoarea litera

        ++i;
    }

    fout << e << '\n';
    for(int j = 1; j <= e && j <= 1000; j++)
        fout << ans[j] << " ";

    return 0;
}