Cod sursa(job #3214619)

Utilizator popuPop Matei Tudor popu Data 14 martie 2024 11:33:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <bits/stdc++.h>

#define ll unsigned long long

using namespace std;

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

const ll M1 = 269696969;
const ll M2 = 1000000009;
string a, b;
ll P1 = 67, P2 = 317, lastBase1, c, hashA1, hashB1, invP1, n, hashA2, hashB2, lastBase2, invP2, la, lb;
vector<int> res;

ll logput(ll x, ll exp, ll M)
{
    ll aux = 1;
    while(exp)
    {
        if(exp % 2)
            aux = aux * x % M;
        exp /= 2;
        x = x * x % M;
    }
    return aux;
}

ll makeHash(string s, int start, int stop, ll P, ll M)
{
    ll rez = 0;
    ll aux = 1;

    for(int i = start; i < stop; i++)
    {
        rez = (rez + (aux * s[i] % M)) % M;
        aux = aux * P % M;
    }

    return rez;
}

bool check(int st)
{
    int i = 0;
    while(i < la)
    {
        if(a[i] != b[st])
            return 0;
        i++;
        st++;
    }
    return 1;
}

int main()
{
    fin >> a >> b;

    la = a.length();
    lb = b.length();

    lastBase1 = logput(P1, la - 1, M1);
    invP1 = logput(P1, M1 - 2, M1);
    lastBase2 = logput(P2, la - 1, M2);
    invP2 = logput(P2, M2 - 2, M2);

    if(la > lb)
    {
        fout << 0;
        return 0;
    }

    hashA1 = makeHash(a, 0, la, P1, M1);
    hashB1 = makeHash(b, 0, la, P1, M1);
    hashA2 = makeHash(a, 0, la, P2, M2);
    hashB2 = makeHash(b, 0, la, P2, M2);

    for(int i = la - 1; i < lb; i++)
    {
        if(hashA1 == hashB1 && hashA2 == hashB2)
            res.push_back(i - la + 1);

        hashB1 = (hashB1 - b[i - la + 1] + M1) % M1;
        hashB1 = hashB1 * invP1 % M1;
        hashB1 = (hashB1 + b[i + 1] * lastBase1 % M1) % M1;

        hashB2 = (hashB2 - b[i - la + 1] + M2) % M2;
        hashB2 = hashB2 * invP2 % M2;
        hashB2 = (hashB2 + b[i + 1] * lastBase2 % M2) % M2;
    }

    fout << res.size() << '\n';
    n = res.size();
    if(res.size() > 1000)
        n = 1000;
    for(int i = 0; i < n; i++)
        fout << res[i] << ' ';

    return 0;
}