Cod sursa(job #2883873)

Utilizator PatrascuAdrian1Patrascu Adrian Octavian PatrascuAdrian1 Data 1 aprilie 2022 22:16:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <string>
#include <vector>
#include <cctype>
#include <unordered_map>

using namespace std;

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

const int nrlitalfabet = 62, MOD = 1999999973;
long long add(long long a, long long b)
{
    long long res = a + b;

    while (res >= MOD)
        res -= MOD;

    while (res < 0)
        res += MOD;

    return res;
}

int main()
{
    string a, b;
    vector <int> rez(1000, 0);
    int chei[250];
    fin >> a;
    fin >> b;
    int lung = a.length(), i, j, k=0;
    long long hasha=0, putmic = 1, hashb = 0, hashbnou;
    char test;
    j = 1;
    for (test = 'a'; test <= 'z'; test++, j++)
        chei[test] = j;
    for (test = 'A'; test <= 'Z'; test++, j++)
        chei[test] = j;
    for (test = '0'; test <= '9'; test++, j++)
        chei[test] = j;
    if (a.length() > b.length())
        fout << 0;
    else
    {
        for(i = lung-1; i >=1; i--)
        {
            hasha = add(hasha + putmic * chei[a[i]], MOD);
            hashb = add(hashb + putmic * chei[b[i]], MOD);
            putmic = add(putmic * nrlitalfabet, MOD);
        }
        hasha = add(hasha + putmic * chei[a[0]],MOD);
        hashb = add(hashb + putmic * chei[b[0]],MOD);
        if (hasha == hashb)
        {
            rez[k++] = 0;
        }
        hashbnou = hashb;
        for (i = lung; i < b.length(); i++)
        {
            j = i - lung + 1;
            //hashbnou = (MOD + hashbnou - (chei[b[j - 1]] * putmic % MOD) * nrlitalfabet % MOD + chei[b[i]]) % MOD;
            hashbnou = ((MOD + hashbnou - (chei[b[j-1]] * putmic) % MOD) % MOD * nrlitalfabet + chei[b[i]]) % MOD;
            if (hashbnou == hasha)
            {
                if (k < 1000)
                    rez[k++] = j;
            }
        }
        fout << k << '\n';
        for (i = 0; i < min(k, 1000); i++)
        {
            fout << rez[i] << ' ';
        }
    }


    return 0;
}