Cod sursa(job #3214450)

Utilizator popuPop Matei Tudor popu Data 14 martie 2024 09:42:00
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 kb
#include <bits/stdc++.h>

#define ll unsigned long long
#define M 1000000007
#define M2 1000000009

using namespace std;

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

string a, b;
ll P = 307, P2 = 317, lastBase = 1, c, hashA, hashB, invP, n, hashA2, hashB2, lastBase2, invP2;
vector<int> res;

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

ll makeHash(string s, int start, int stop)
{
    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;
}

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

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

    return rez;
}

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

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

    lastBase = logput(P, a.length() - 1, M);
    invP = logput(P, M - 2, M);
    lastBase2 = logput(P2, a.length() - 1, M2);
    invP2 = logput(P2, M2 - 2, M2);

    if(a.length() > b.length())
    {
        fout << 0;
        return 0;
    }

    hashA = makeHash(a, 0, a.length());
    hashB = makeHash(b, 0, a.length());
    hashA2 = makeHash2(a, 0, a.length());
    hashB2 = makeHash2(b, 0, a.length());

    for(int i = a.length() - 1; i < b.length(); i++)
    {
        if(hashA == hashB && hashA2 == hashB2 && check(i - a.length() + 1))
            res.push_back(i - a.length() + 1);

        hashB = (hashB - b[i - a.length() + 1] + M) % M;
        hashB = hashB * invP % M;
        hashB = (hashB + b[i + 1] * lastBase % M) % M;

        hashB2 = (hashB2 - b[i - a.length() + 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;
}