Cod sursa(job #2793605)

Utilizator mateitudordmDumitru Matei mateitudordm Data 3 noiembrie 2021 19:52:35
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 kb
#include <bits/stdc++.h>
#define mod1 16127
#define mod2 16128
#define baza 63
#pragma GCC optimize("O3")

using namespace std;

int put1 = 1, put2 = 1, v[2000001];
int makehash(const string &a, int mod)
{
    int nr = 0, i;
    for (i = 0; i < a.size(); i++)
    {
        if (a[i] >= 'a' && a[i] <= 'z')
            nr = (nr * baza + a[i] - 'a' + 1) % mod;
        else if (a[i] >= 'A' && a[i] <= 'Z')
            nr = (nr * baza + a[i] - 'A' + 27) % mod;
        else
            nr = (nr * baza + a[i] - '0' + 53) % mod;
    }
    return nr;
}
int remove(int a, int i, const string &s, int mod, int put)
{
    if (s[i] >= 'a' && s[i] <= 'z')
        a -= (s[i] - 'a' + 1) * put % mod;
    else if (s[i] >= 'A' && s[i] <= 'Z')
        a -= (s[i] - 'A' + 27) * put % mod;
    else
        a -= (s[i] - '0' + 53) * put % mod;
    while (a < 0)
        a += mod;
    return a;
}
int add(int a, int i, const string &s, int mod)
{
    a = a * baza % mod;
    if (s[i] >= 'a' && s[i] <= 'z')
        a = (a + s[i] - 'a' + 1) % mod;
    else if (s[i] >= 'A' && s[i] <= 'Z')
        a = (a + s[i] - 'A' + 27) % mod;
    else
        a = (a + s[i] - '0' + 53) % mod;
    return a;
}
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string a, b;
    int ha1 = 0, hb1 = 0, ha2 = 0, hb2 = 0, cnt = 0, i, p = 0;
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> a >> b;
    if (a.size() <= b.size())
    {
        ha1 = makehash(a, mod1);
        hb1 = makehash(b.substr(0, a.size()), mod1);
        ha2 = makehash(a, mod2);
        hb2 = makehash(b.substr(0, a.size()), mod2);
        for (i = 0; i < a.size() - 1; i++)
            put1 = (put1 * baza) % mod1, put2 = (put2 * baza) % mod2;
        if (hb1 == ha1 && ha2 == hb2)
            if (a == b.substr(0, a.size()))
                v[p++] = 0;
        for (i = 0; i < b.size() - a.size(); i++)
        {
            hb1 = remove(hb1, i, b, mod1, put1);
            hb1 = add(hb1, i + a.size(), b, mod1);
            hb2 = remove(hb2, i, b, mod2, put2);
            hb2 = add(hb2, i + a.size(), b, mod2);
            if (hb1 == ha1 && ha2 == hb2)
                if (a == b.substr(i + 1, a.size()))
                    v[p++] = i + 1;
        }
    }
    cout << p << '\n';
    for (i = 0; i < min(p, 1000); i++)
        cout << v[i] << ' ';
    return 0;
}