Cod sursa(job #2880489)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 29 martie 2022 19:48:52
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <string>
#include <vector>
#include <cctype>

using namespace std;

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

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