Cod sursa(job #3293639)

Utilizator robert_dumitruDumitru Robert Ionut robert_dumitru Data 12 aprilie 2025 10:44:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define Mod 1000000891
using namespace std;

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

int n, m;
string A, B;
vector<int> sol;

int CharToInt(char ch)
{
    if ('a' <= ch && ch <= 'z') return ch - 'a';
    if ('A' <= ch && ch <= 'Z') return ch - 'A' + 26;
    return ch - '0' + 52;
}

int main()
{
    int i;
    long long h1, h2, P;
    string aux;

    fin >> A >> B;
    n = A.length(); m = B.length();
    aux = " " + A;
    A  = aux;
    aux = " " + B;
    B = aux;

    P = 1;
    h1 = h2 = 0;
    for (i = 1; i <= n; i++)
    {
        h1 = (h1 * 62 + CharToInt(A[i])) % Mod;
        h2 = (h2 * 62 + CharToInt(B[i])) % Mod;
        if (i != n) P = P * 62 % Mod;
    }
    if (h1 == h2)
        sol.push_back(0);
    for (i = n + 1; i <= m; i++)
    {
        h2 = (h2 - P * CharToInt(B[i - n]) % Mod + Mod) % Mod;
        h2 = (h2 * 62 + CharToInt(B[i])) % Mod;

        if (h1 == h2) sol.push_back(i - n);
    }
    n = sol.size();
    fout << n << "\n";
    for (i = 0; i < min(1000, n); i++)
        fout << sol[i] << " ";
    return 0;
}