Cod sursa(job #2881443)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 30 martie 2022 15:10:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 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(1000, 0);
    unordered_map <char, int> chei;
    fin >> a;
    fin >> b;
    int nrlitalfabet = 62, prim = 1999999973, 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 = (hasha + putmic * chei[a[i]])%prim;
            hashb = (hashb + putmic * chei[b[i]])%prim;
            putmic = (putmic * nrlitalfabet) % prim;
        }
        hasha = (hasha + putmic * chei[a[0]])%prim;
        hashb = (hashb + putmic * chei[b[0]])%prim;
        if (hasha == hashb)
        {
            rez[k++] = 0;
        }
        hashbnou = hashb;
        for (i = lung; i < b.length(); i++)
        {
            j = i - lung + 1;
            hashbnou = ((prim + hashbnou - chei[b[j-1]] * putmic%prim) % prim *nrlitalfabet + chei[b[i]])%prim;
            if (hashbnou == hasha)
            {
                if (k < 1000)
                    rez[k] = j;
                k++;
            }

        }
        fout << k << '\n';
        for (i = 0; i < k && i < 1000; i++)
        {
            fout << rez[i] << ' ';
        }
    }


    return 0;
}