Cod sursa(job #2675196)

Utilizator razvanradulescuRadulescu Razvan razvanradulescu Data 21 noiembrie 2020 11:06:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <string>
#include <vector>
#define A 31
#define MOD1 100003
#define MOD2 100109
using namespace std;

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

struct RollingHash
{
    int a, mod, aMax;
    int value;

    RollingHash(int a, int mod)
    {
        this->a = a;
        this->mod = mod;
        aMax = 1;
        value = 0;
    }

    void initHash(const string &s)
    {
        for(int i = 0; i<s.size(); i++)
        {
            value = (value * a + s[i])%mod;
            if(i)
            aMax = (aMax * a)%mod;
        }
    }

    void roll(char in, char out)
    {
        value = ((value - (out * aMax) % mod + mod) * a + in) % mod;
    }

    bool operator ==(RollingHash other)
    {
        return value == other.value;
    }
};

vector<int> sol;
int k;

void debug(RollingHash r1, RollingHash r2, RollingHash r3, RollingHash r4)
{
    g<<r1.value<<" "<<r2.value<<"\n";
    g<<r3.value<<" "<<r4.value<<"\n";
    g<<"\n";
}

void solve()
{
    RollingHash pattern1 = RollingHash(A, MOD1), pattern2 = RollingHash(A, MOD2);
    RollingHash text1 = RollingHash(A, MOD1), text2 = RollingHash(A, MOD2);

    string pattern, text;
    f>>pattern>>text;
    if(pattern.size() > text.size())
    {
        return;
    }

    pattern1.initHash(pattern);
    pattern2.initHash(pattern);
    text1.initHash(text.substr(0, pattern.size()));
    text2.initHash(text.substr(0, pattern.size()));

    if(pattern1 == text1 && pattern2 == text2)
    {
        k++;
        sol.push_back(0);
    }
    for(int i = pattern.size(); i < text.size(); i++)
    {
        text1.roll(text[i], text[i - pattern.size()]);
        text2.roll(text[i], text[i - pattern.size()]);
        if(pattern1 == text1 && pattern2 == text2)
        {
            k++;
            if(sol.size() < 1000)
                sol.push_back(i - pattern.size() + 1);
        }
    }
}


void afisare()
{
    g<<k<<"\n";
    for(int i = 0; i<sol.size(); i++)
        g<<sol[i]<<" ";
}

int main()
{
    solve();
    afisare();
    return 0;
}