Cod sursa(job #3269877)

Utilizator miu_anaMiu Ana Corina miu_ana Data 21 ianuarie 2025 12:30:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.37 kb
#include <fstream>
#include <cstring>

using namespace std;

/**
'0' = 0
'1' = 1
...
'9' = 9
'A' = 10
'B' = 11
...
'Z' = 35
'a' = 36
'b' = 37
...
'z' = 61
*/

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

char a[2000005], b[2000005];
int n, m, sol[2000005], lungime;
int main()
{
    int i, codap, codbp, j, p62, q62;
    int codaq, codbq;
    int B = 62;
    long long P = 1000007, Q = 666013;
    cin >> a >> b;
    n = strlen(a); m = strlen(b);
    /// formam p62, q62 = B^(n-1)
    p62 = q62 = 1;
    for (i = 1; i < n; i++)
    {
        p62 = p62 * B % P;
        q62 = q62 * B % Q;
    }
    /// formam codul asociat lui a
    codap = codaq = 0;
    for (i = 0; i < n; i++)
    {
        if (a[i] <= '9')
            j = a[i] - '0';
        else
            if (a[i] <= 'Z')
                j = a[i] - 'A' + 10;
            else
                j = a[i] - 'a' + 36;
        codap = (codap * B + j) % P;
        codaq = (codaq * B + j) % Q;
    }
    /// formam primul codb si codb1
    codbp = codbq = 0;
    for (i = 0; i < n; i++)
    {
        if (b[i] <= '9')
            j = b[i] - '0';
            else
                if (b[i] <= 'Z')
                    j = b[i] - 'A' + 10;
                else
                    j = b[i] - 'a' + 36;
        codbp = (codbp * B + j) % P;
        codbq = (codbq * B + j) % Q;
    }
    if (codbp == codap && codbq == codaq)
        sol[++lungime] = 0;
    for (i = n; i < m; i++)
    {
        /// adaugam cifra b[i], scoatem b[i-n]
        if (b[i-n] <= '9')
            j = b[i-n] - '0';
            else
                if (b[i-n] <= 'Z')
                    j = b[i-n] - 'A' + 10;
                else
                    j = b[i-n] - 'a' + 36;

        codbp = (codbp - j * p62 % P + P) * B;
        codbq = (codbq - j * q62 % Q + Q) * B;

        if (b[i] <= '9')
            j = b[i] - '0';
            else
                if (b[i] <= 'Z')
                    j = b[i] - 'A' + 10;
                else
                    j = b[i] - 'a' + 36;

        codbp = (codbp + j) % P;
        codbq = (codbq + j) % Q;

        if (codbp == codap && codbq == codaq)
            sol[++lungime] = i - n + 1;
    }
    cout << lungime << "\n";
    lungime = min(lungime, 1000);
    for (i = 1; i <= lungime; i++)
        cout << sol[i] << " ";
    return 0;
}