Cod sursa(job #3279036)

Utilizator vicvicGriga Victor-Cristian vicvic Data 21 februarie 2025 18:31:51
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <string>
#include <cstring>
#include <cstdint>
#include <vector>
#include <fstream>
#define int long long
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
class Hash
{
public:
    int hsh=0, ptr=0, lim, mod, p, imp=0;
    string s;
    int lgpow (int a, int b)
    {
        if (b==0)
            return 1;
        if (b%2==0)
        {
            int p=lgpow (a, b/2);
            return (p%mod)*(p%mod)%mod;
        }
        return (lgpow (a, b-1)%mod)*(a%mod)%mod;
    }
    Hash ()
    {

    }
    void make (string s, int mod, int p)
    {
        this -> mod=mod;
        this -> p=p;
        this -> lim=s.size();
        this -> s=s;
        for (int i=0;i<s.size();i++)
        {
            hsh+=s[i]*lgpow (p, ((int)s.size()-i-1));
            hsh%=mod;
        }
        this -> imp=lgpow (p, lim-1);
    }
    void roll (char ch)
    {
        hsh-=s[this -> ptr++]*imp;
        hsh=(hsh+mod)%mod;
        hsh*=p;
        hsh%=mod;
        hsh+=(int)ch;
        hsh%=mod;
        s+=ch;
    }
};
vector <int> vec;
Hash a, a1, b, b1;
string s, s1;
int32_t main ()
{
    f >> s >> s1;
    a.make (s, 31, 400099);
    b.make (string (s1.begin(), s1.begin()+s.size()), 31, 400099);
    a1.make (s, 53, 310993);
    b1.make (string (s1.begin(), s1.begin()+s.size()), 53, 310993);
    if (a.hsh==b.hsh && a1.hsh==b1.hsh)
    {
        vec.push_back (0);
    }
    for (int i=(int)s.size();i<s1.size();i++)
    {
        b.roll (s1[i]);
        b1.roll (s1[i]);
        if (a.hsh==b.hsh && a1.hsh==b1.hsh)
        {
            vec.push_back (i-s.size()+1);
        }
    }
    g << vec.size() << "\n";
    for (int i=0;i<vec.size() && i<1000;i++)
    {
        g << vec[i] << " ";
    }
    return 0;
}