Cod sursa(job #1649828)

Utilizator BrandonChris Luntraru Brandon Data 11 martie 2016 15:17:57
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <string>

#define NMAX 2000005
#define BASE 101
#define MOD1 100007
#define MOD2 100021
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string A, B;

int hash1_A, hash2_A, hash1_B, hash2_B, reh_base1, reh_base2, ans_nr;
bool match[NMAX];

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

    if(A.size() > B.size()) {
        cout << 0 << '\n';
        return 0;
    }

    reh_base1 = reh_base2 = 1;

    for(int i = 0; i < (int) A.size(); ++i) {
        hash1_A = (hash1_A * BASE + A[i]) % MOD1;
        hash2_A = (hash2_A * BASE + A[i]) % MOD2;

        if(i) {
            reh_base1 = (reh_base1 * BASE) % MOD1;
            reh_base2 = (reh_base2 * BASE) % MOD2;
        }
    }

    for(int i = 0; i < (int) A.size(); ++i) {
        hash1_B = (hash1_B * BASE + B[i]) % MOD1;
        hash2_B = (hash2_B * BASE + B[i]) % MOD2;
    }

    for(int i = (int) A.size(); i < (int) B.size(); ++i) {
        hash1_B = hash1_B - (B[i - A.size()] * reh_base1) % MOD1 + MOD1;
        hash1_B = (hash1_B * BASE + B[i]) % MOD1;

        hash2_B = hash2_B - (B[i - A.size()] * reh_base2) % MOD2 + MOD2;
        hash2_B = (hash2_B * BASE + B[i]) % MOD2;

        if(hash1_A == hash1_B and hash2_A == hash2_B) {
            match[i - A.size()] = true;
            ++ans_nr;
        }
    }

    cout << ans_nr << '\n';
    ans_nr = min(ans_nr, 1000);

    for(int i = 0; i < (int) B.size() and ans_nr; ++i) {
        if(!match[i]) {
            continue;
        }

        --ans_nr;
        cout << i + 1 << ' ';
    }

    cout << '\n';
    return 0;
}