Cod sursa(job #2985197)

Utilizator dragos24Dragos-Andrei Baiu dragos24 Data 25 februarie 2023 21:19:28
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

long int P=17,M=1000000007;
vector<int> results;

long int pH(string a)
{
    int p=1,rez=0;
    for (int i=a.size()-1;i>=0;i--)
    {
        rez=rez+p*a[i];
        p=p*P;
        p=p%M;
        rez=rez%M;
    }
    return rez;
}

int main()
{
    string S,g;
    in >> g >> S;

    if(g.size() > S.size())
    {
        out << '0' << '\n';
        return 0;
    }

    long int hashg=pH(g);
    string test=S.substr(0,g.size());
    long int hashTest=pH(test);

    long int putere=1;
    for (int i=1; i<=g.size()-1; i++)
    {
        putere=putere*P;
    }

    long int ct=0,oldHash=hashTest;

    if (hashg==hashTest)
    {
        ct++;
        results.push_back(0);
    }
    //out << hashg << '\n' << '\n';
    //out << putere << '\n';
    //out << hashTest << '\n' << '\n';
    for (int i = 1; i < S.size() - g.size() + 1; i++)
    {
        string temp = S.substr(i, g.size());
        //out << temp << '\n';
        //out << S[i-1] << " " << S[g.size() + i - 1] << '\n';
        long int newHash=(oldHash-S[i-1]*putere)*P+S[g.size()+i-1];
        newHash=newHash%M;
        //out << newHash << '\n';
        long int temph = pH(temp);
        //out << temph << '\n' << '\n';

        if (newHash==hashg)
        {
           ct++;
           if(results.size() < 1000)
           {
               results.push_back(i);
           }
        }
        oldHash=newHash;
    }
    out << ct << '\n';
    for(int i =0; i < results.size(); i++)
    {
        out << results[i] << " ";
    }
    out << '\n';
    return 0;
}