Cod sursa(job #2985491)

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

using namespace std;

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

int P=17,M=100007;
vector<int> results;

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

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

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

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

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

    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';
        int toDecrease = S[i-1]*putere % M;
        int diff = (oldHash-toDecrease);
        if(diff < 0)
        {
            diff += M;
        }
        int newHash=(diff*P)%M+S[g.size()+i-1];
        newHash=newHash%M;
        // out << newHash << '\n';
        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;
}