Cod sursa(job #3260985)

Utilizator Robert2566_Lungu Robert Robert2566_ Data 4 decembrie 2024 09:20:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <bits/stdc++.h>


#define B 62
#define P 10000019
#define Q 777013
using namespace std;

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

/**
'0' = 0
'1' = 1
...
'9' = 9
'A' = 10
'B' = 11
...
'Z' = 35
'a' = 36
'b' = 37
...
'z' = 61
*/
char a[2000005], b[2000005];
int n, m, sol[2000005], len;
int main()
{
    int i, coda, codb, j, p62, q62;
    int coda1, codb1;
    fin >> a >> b;
    n = strlen(a); m = strlen(b);
    /// formam p62 = 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
    coda = coda1 = 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;
        coda = (coda * B + j) % P;
        coda1 = (coda1 * B + j) % Q;
    }
    /// formam primul codb si codb1
    codb = codb1 = 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;
        codb = (codb * B + j) % P;
        codb1 = (codb1 * B + j) % Q;
    }
    if (codb == coda && codb1 == coda1)
        sol[++len] = 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;

        codb = (codb - j * p62 % P + P) * B;
        codb1 = (codb1 - 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;

        codb = (codb + j) % P;
        codb1 = (codb1 + j) % Q;

        if (codb == coda && codb1 == coda1)
            sol[++len] = i - n + 1;
    }
    fout << len << "\n";
    for (i = 1; i <= len; i++)
        fout << sol[i] << " ";
    return 0;
}