Cod sursa(job #1933848)

Utilizator serbanSlincu Serban serban Data 20 martie 2017 23:00:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>

using namespace std;

const int mod1 = 31883;
const int mod2 = 31891;
int h1, h2;
int a1, a2;

vector<int> ret;

int inv1, inv2;

void calc1() {
    int a = 131, b = 1, n = mod1 - 2;
    while(n) {
        if(n % 2 == 1) b *= a, b %= mod1;
        a *= a; a %= mod1;
        n /= 2;
    }
    inv1 = b;
}

void calc2() {
    int a = 131, b = 1, n = mod2 - 2;
    while(n) {
        if(n % 2 == 1) b *= a, b %= mod2;
        a *= a; a %= mod2;
        n /= 2;
    }
    inv2 = b;
}

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    string A; f >> A;
    int n = A.size();

    string B; f >> B;
    int m = B.size();

    if(n > m) {
        g << "0\n";
        return 0;
    }

    int p1 = 1, p2 = 1;
    h1 = (A[0] - '0' + 1);
    h2 = (A[0] - '0' + 1);

    for(int i = 1; i < n; i ++) {
        p1 *= 131; p1 %= mod1;
        p2 *= 131; p2 %= mod2;
        h1 = (h1 + (A[i] - '0' + 1) * p1) % mod1;
        h2 = (h2 + (A[i] - '0' + 1) * p2) % mod2;
    }

    p1 = 1; p2 = 1;
    a1 = (B[0] - '0' + 1);
    a2 = (B[0] - '0' + 1);
    for(int i = 1; i < n; i ++) {
        p1 *= 131; p1 %= mod1;
        p2 *= 131; p2 %= mod2;
        a1 = (a1 + (B[i] - '0' + 1) * p1) % mod1;
        a2 = (a2 + (B[i] - '0' + 1) * p2) % mod2;
    }

    if(a1 == h1 && a2 == h2) {
        ret.push_back(0);
    }

    calc1();
    calc2();

    for(int i = n; i < m; i ++) {
        a1 = a1 - (B[i - n] - '0' + 1);
        a2 = a2 - (B[i - n] - '0' + 1);

        a1 *= inv1; a1 %= mod1;
        a2 *= inv2; a2 %= mod2;

        a1 = (a1 + (B[i] - '0' + 1) * p1) % mod1;
        a2 = (a2 + (B[i] - '0' + 1) * p2) % mod2;

        if(a1 == h1 && a2 == h2) {
            ret.push_back(i - n + 1);
        }
    }

    g << ret.size() << "\n";
    int lim = min(1000, (int)ret.size());
    for(int i = 0; i < lim; i ++) g << ret[i] << " ";
    g << "\n";
    return 0;
}