Cod sursa(job #3363210)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 14 august 2026 12:46:32
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <bits/stdc++.h>
using namespace std;
const int BAZA = 67;
const int MOD = 1e9 + 7;
const int CIF_MAX = 1000000;
int inv[CIF_MAX + 1], v[CIF_MAX + 1];
long long h[CIF_MAX + 1];
int cod(char c)
{
    if(c >= '0' && c <= '9')
    {
        return c - '0';
    }
    else if(c >= 'a' && c <= 'z')
    {
        return c - 'a' + 10;
    }
    else
    {
        return c - 'A' + 36;
    }
}
int hs(string s, int b)
{
    int put, nr = 1;
    put = 1;
    for(int i = 0; i < s.size(); i++)
    {
        nr = (1LL * nr + ((1LL * cod(s[i] - '0') * put) % MOD)) % MOD;
        put = (1LL * put * b) % MOD;
    }
    return nr;
}
int hp(string s, int b)
{
    int put = 1, nr = 1;
    for(int i = 0; i < s.size(); i++)
    {
        nr = (1LL * nr + ((1LL * cod(s[i] - '0') * put) % MOD)) % MOD;
        put = 1LL * put * b % MOD;
        h[i + 1] = (1LL * h[i] + nr);
    }
    return nr;
}
int put(int a, int b)
{
    if(b == 1)
        return a;
    if(b == 0)
        return 1;
    if(b % 2 == 1)
    {
        return 1LL * (1LL * put(1LL * a * a % MOD, b / 2) * a % MOD) * a % MOD;
    }
    else
    {
        int rez = put(a, b / 2);
        return 1LL * rez * rez % MOD;
    }
}
signed main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int ha, hb, poz = 0, chb = 0, lenb = 0, ap = 0;
    string a, b;
    char c;
    cin >> b >> a;
    cin >> a >> b;
    hb = hs(b, BAZA);
    chb = hb;
    while(chb > 0)
    {
        chb /= 10;
        lenb++;
    }
    ha = hp(a, BAZA);
    for(int i = 0; i <= CIF_MAX; i++)
    {
        inv[i] = put(BAZA, 1LL * i * (MOD - 2) % MOD);
    }
    lenb = b.size();
    inv[0] = 1;
    for(int i = lenb; i <= a.size(); i++)
    {
        if(1LL * (h[i] - h[i - lenb] + MOD) * inv[i - lenb + 1] % MOD == hb)
        {
            if(ap <= 1000)
                v[ap++] = i - lenb + 1;
            else
                ap++;
        }
    }
    cout << ap << "\n";
    for(int i = 0; i < min(ap, 1000); i++)
    {
        cout << v[i] << " ";
    }
    //cout << (1LL * h[8] - h[5] + MOD) % MOD * inv[6] % MOD << " " << hb;
    return 0;
}