Cod sursa(job #3151134)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 19 septembrie 2023 20:39:09
Problema Potrivirea sirurilor Scor 72
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MOD = 1e9 + 7;
int pref[2000001];

int afis[2000001];

int main()
{
    string a, b;
    in >> a >> b;
    int nr = 0, cnt = 0;
    for(int i = 1; i <= a.size(); i++)
        nr = (27LL * nr + (a[i - 1] - 'A' + 1)) % MOD;
    for(int i = 1; i <= b.size(); i++)
        pref[i] = (27LL * pref[i - 1] + (b[i - 1] - 'A' + 1)) % MOD;
    int put = 1;
    for(int i = 1; i <= a.size(); i++)
        put = 27LL * put % MOD;
    for(int i = a.size(); i <= b.size(); i++)
        if((pref[i] - 1LL * put * pref[i - a.size()] % MOD + MOD) % MOD == nr)
        {
            cnt++;
            if(cnt <= 1000)
                afis[cnt] = i - a.size();
        }
    out << cnt << '\n';
    for(int i = 1; i <= min(cnt, 1000); i++)
        out << afis[i] << " ";
    return 0;
}