Cod sursa(job #2768809)

Utilizator NuSuntRomanIspir Alexandru NuSuntRoman Data 12 august 2021 11:38:58
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 kb
#include <fstream>
#include <vector>

using namespace std;

const long long int modx = 1000000007;
const long long int mody = 1000000009;

int cnt;

string A, B;
vector < int > ans;

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

long long int exp(long long int b, long long int e, long long int mod) {
    if (e == 0)
        return 1;

    if (!(e & 1))
        return exp(((b % mod) * (b % mod)) % mod, (e >> 1), mod) % mod;
    else
        return ((b % mod) * (exp(((b % mod) * (b % mod)) % mod, (e >> 1), mod) % mod)) % mod;
}

long long int inv_mod(long long int a, long long int mod) {
    return exp(a, mod - 2, mod) % mod;
}

long long int value(char x) {
    if ('A' <= x && x <= 'Z')
        return x - 'A';
    if ('a' <= x && x <= 'z')
        return x - 'a' + 26;
    if ('0' <= x && x <= '9')
        return x - '0' + 52;
}

int main() {
    fin >> A >> B;

    if (A.size() > B.size()) {
        fout << "0";
        return 0;
    }
    else {
        long long int px = 1, py = 1, hashx = 0, hashy = 0, hx = 0, hy = 0;

        for (int i = 0; i < A.size(); ++ i, px = (px * 62) % modx, py = (py * 62) % mody) {
            hashx = (hashx % modx + (px * value(A[i])) % modx) % modx;
            hashy = (hashy % mody + (py * value(A[i])) % mody) % mody;
        }

        int invx = inv_mod(62, modx), invy = inv_mod(62, mody);

        for (int i = 0, px = 1, py = 1; i < A.size(); ++ i, px = (px * 62) % modx, py = (py * 62) % mody) {
            hx = (hx % modx + (px * value(B[i])) % modx) % modx;
            hy = (hy % mody + (py * value(B[i])) % mody) % mody;
        }

        px = (px * invx) % modx;
        py = (py * invy) % mody;

        if (hx == hashx && hy == hashy) {
            ++ cnt;
            ans.push_back(0);
        }

        for (int i = A.size(); i < B.size(); ++ i) {
            hx = (((hx - value(B[i - A.size()]) + modx) % modx * invx) % modx + (value(B[i]) * px) % modx) % modx;
            hy = (((hy - value(B[i - A.size()]) + mody) % mody * invy) % mody + (value(B[i]) * py) % mody) % mody;

            if (hx == hashx && hy == hashy) {
                ++ cnt;
                ans.push_back(i - A.size() + 1);
            }
        }

        fout << cnt << "\n";

        for (int i = 0; i < min(1000, cnt); ++ i)
            fout << ans[i] << " ";
    }

    return 0;
}