Cod sursa(job #2883885)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 1 aprilie 2022 22:21:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 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);
    int chei[150];
    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) *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;
}