Cod sursa(job #2985521)

Utilizator sicsicFMI-Coteanu Vlad sicsic Data 26 februarie 2023 16:17:13
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

int P=17,M1=100007, M2=100021;
vector<int> results;

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

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

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

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

    int hashg1=pH1(g), hashg2=pH2(g);
    string test=S.substr(0,g.size());
    int hashTest1=pH1(test), hashTest2=pH2(test);

    int putere1=1, putere2 = 1;
    for (int i=1; i<=g.size()-1; i++)
    {
        putere1=(putere1*P)%M1;
        putere2 = (putere2*P)%M2;
    }

    int ct=0,oldHash1 = hashTest1, oldHash2 = hashTest2;

    if (hashg1==hashTest1 && hashg2 == hashTest2)
    {
        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';
        int newHash1 = ((oldHash1 - S[i-1]*putere1)%M1 + M1) * P + S[g.size()+i-1];
        newHash1=newHash1%M1;

        int newHash2 = ((oldHash2 - S[i-1]*putere2)%M2 + M2) * P + S[g.size()+i-1];
        newHash2=newHash2%M2;
        //out << newHash << '\n';
        //int temph = pH(temp);
        //out << temph << '\n' << '\n';

        if (newHash1==hashg1 && newHash2==hashg2)
        {
           ct++;
           if(results.size() < 1000)
           {
               results.push_back(i);
           }
        }
        oldHash1=newHash1;
        oldHash2=newHash2;
    }
    out << ct << '\n';
    for(int i =0; i < results.size(); i++)
    {
        out << results[i] << " ";
    }
    out << '\n';
    return 0;
}