Cod sursa(job #3214354)

Utilizator PalcPalcu Stefan Palc Data 14 martie 2024 08:37:10
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.14 kb
#include <bits/stdc++.h>
#define P 123457
#define Q 777013
using namespace std;

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

int n, m, cnt, codA1, codA2, codB1, codB2, p1, p2;;
vector<int> sol;
string a, b;

int main()
{
    int i;
    fin >> a;
    fin >> b;
    n = a.size();
    m = b.size();
    p1 = p2 = 1;
    for (i = 0; i < n; i++)
    {
        if (a[i] >= 'A' && a[i] <= 'Z')
        {
            codA1 = (codA1 * 36 + (a[i] - 'A')) % P;
            codA2 = (codA2 * 36 + (a[i] - 'A')) % Q;
        }
        else
        {
            codA1 = (codA1 * 36 + (a[i] - '0') + 26) % P;
            codA2 = (codA2 * 36 + (a[i] - '0') + 26) % Q;
        }
        if (b[i] >= 'A' && b[i] <= 'Z')
        {
            codB1= (codB1 * 36 + (b[i] - 'A')) % P;
            codB2 = (codB2 * 36 + (b[i] - 'A')) % Q;
        }
        else
        {
            codB1 = (codB1 * 36 + (b[i] - '0') + 26) % P;
            codB2 = (codB2 * 36 + (b[i] - '0') + 26) % Q;
        }
        if (i > 0)
        {
            p1 = (p1 * 36) % P;
            p2 = (p2 * 36) % Q;
        }
    }
    if (codA1 == codB1 && codA2 == codB2)
    {
        cnt++;
        sol.push_back(1);
    }
    for (i = n; i < m; i++)
    {
        if (b[i - n] >= 'A' && b[i - n] <= 'Z')
        {
            codB1 = (codB1 - (b[i - n] - 'A') * p1 % P + P) % P;
            codB2 = (codB2 - (b[i - n] - 'A') * p2 % Q + Q) % Q;
        }
        else
        {
            codB1 = (codB1 - ((b[i - n] - '0') + 26) * p1 % P + P) % P;
            codB2 = (codB2 - ((b[i - n] - '0') + 26) * p2 % Q + Q) % Q;
        }
        if (b[i] >= 'A' && b[i] <= 'Z')
        {
            codB1= (codB1 * 36 + (b[i] - 'A')) % P;
            codB2 = (codB2 * 36 + (b[i] - 'A')) % Q;
        }
        else
        {
            codB1 = (codB1 * 36 + (b[i] - '0') + 26) % P;
            codB2 = (codB2 * 36 + (b[i] - '0') + 26) % Q;
        }
        if (codA1 == codB1 && codA2 == codB2)
        {
            cnt++;
            sol.push_back(i - n + 1);
        }
    }
    fout << cnt << "\n";
    for (int e : sol)
        fout << e << " ";
    fout << "\n";
    fin.close();
    fout.close();
    return 0;
}