Cod sursa(job #2284302)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 17 noiembrie 2018 10:25:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

istream & in = fin;
ostream & out = fout;

string a, b;
int lolle;

int anslen = 0;
int ans[1041];

int Kapow(int a, int p)
{
    int r = 1;
    for(int i = 0; i < p; i++){
        r *= a;
    }
    return r;
}

struct Thing{
    int n, m, p;
    Thing(int n, int m) : n(n), m(m){}
    void GenP()
    {
        this->p = Kapow(n, lolle-1);
    }
};

Thing t1(3, 20000041), t2(5, 41000041);

void Read()
{
    getline(in, a);
    getline(in, b);
    lolle = a.size();
    t1.GenP(); t2.GenP();
}

int GenHash(const Thing & t, const string & s)
{
    int h = 0;
    for(auto i = s.begin(); i < s.begin()+lolle; i++){
        h *= t.n;
        h += *i;
        h %= t.m;
    }
    return h;
}

//they see me rolling
int Roll(int h, const Thing & t, int pos)
{
    h -= b[pos] * t.p;
    h *= t.n;
    h += b[pos + lolle];
    h %= t.m;
    return h;
}

void Solve()
{
    int c1 = GenHash(t1, a), c2 = GenHash(t2, a);
    int h1 = GenHash(t1, b), h2 = GenHash(t2, b);
    int idk = b.size();
    for(int i = 0; i < idk-lolle; i++){
        if(c1 == h1 && c2 == h2){
            if(anslen < 1000){
                ans[anslen] = i;
            }
            anslen++;
        }
        h1 = Roll(h1, t1, i);
        h2 = Roll(h2, t2, i);
    }
}

void Write()
{
    out << anslen << "\n";
    for(int i = 0; i < anslen; i++){
        out << ans[i] << " ";
    }
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}