Cod sursa(job #2793571)

Utilizator mateitudordmDumitru Matei mateitudordm Data 3 noiembrie 2021 19:05:14
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>
#define mod 666013
#define baza 63

using namespace std;

int put = 1, v[2000001];
int makehash(string a)
{
    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, string s)
{
    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, string s)
{
    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 ha = 0, hb = 0, cnt = 0, i, p = 0;
    cin >> a >> b;
    ha = makehash(a);
    hb = makehash(b.substr(0, a.size()));
    for (i = 0; i < a.size() - 1; i++)
        put = (put * baza) % mod;
    if (hb == ha)
        if (a == b.substr(0, a.size()))
            v[p++] = 0;
    for (i = 0; i < b.size() - a.size(); i++)
    {
        hb = remove(hb, i, b);
        hb = add(hb, i + a.size(), b);
        if (hb == ha)
            if (a == b.substr(i + 1, a.size()))
                v[p++] = i + 1;
    }
    cout << p << '\n';
    for (i = 0; i < p; i++)
        cout << v[i] << ' ';
    return 0;
}