Cod sursa(job #2879841)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 29 martie 2022 01:15:59
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 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 = 26, 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) * (tolower(a[i])-'a'+1)))%prim;
            hashb = (hashb + ((putmic % prim) * (tolower(b[i])-'a'+1))) % 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 - (((tolower(b[j-1])-'a'+1) * putere)%prim))*nrlitalfabet) + (tolower(b[i])-'a'+1))%prim;
            if (hashbnou == hasha)
                rez.push_back(j);
        }
    }
    fout << rez.size() << '\n';
    for (auto i : rez)
        fout << i << ' ';

    return 0;
}