Cod sursa(job #2881330)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 30 martie 2022 14:12:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <string>
#include <vector>
#include <cctype>
#include <unordered_map>

using namespace std;

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

int main()
{
    string a, b;
    vector <int> rez;
    unordered_map <char, int> chei;
    fin >> a;
    fin >> b;
    int nrlitalfabet = 62, prim = 1999999973, lung = a.length(), i, j;
    long long putere = 1, 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;
    for (i = 0; i < lung-1; i++)
    {
        putere = (putere * nrlitalfabet) % prim;
    }
    if (a.length() > b.length())
        fout << 0;
    else
    {
        for(i = lung-1; i >=0 ; i--)
        {
            hasha = (hasha + (putmic * (chei[a[i]])))%prim;
            hashb = (hashb + (putmic % prim * (chei[b[i]])))%prim;
            putmic = (putmic * nrlitalfabet) % prim;

        }
        if (hasha == hashb)
            rez.push_back(0);
        hashbnou = hashb;
        for (i = lung; i < b.length(); i++)
        {
            j = i - lung + 1;
            test = chei[b[j-1]];
            hashbnou = (((prim + hashbnou - (((chei[b[j-1]]) * putere)%prim)) % prim *nrlitalfabet) + (chei[b[i]]))%prim;
            if (hashbnou == hasha)
                rez.push_back(j);

        }
        fout << rez.size() << '\n';
        j = 0;
        for (auto i : rez)
        {
            j++;
            fout << i << ' ';
            if (j > 1000)
                break;
        }
    }


    return 0;
}