Cod sursa(job #1193138)

Utilizator lvamanuLoredana Vamanu lvamanu Data 31 mai 2014 00:54:33
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>

#define MAXN 2000001
#define MOD 100007
#define D   'z'
using namespace std;

bool match[MAXN];

void rabinKarpMatch(string A, string B) {
    int m = A.length();
    int n = B.length();
    int a_m = 1;
    int hashA = 0, hashB_m = 0;
    for (int i = 0; i < m; i++) {
        hashA = ((hashA * D) % MOD + A[i]) % MOD;
        hashB_m = ((hashB_m * D) % MOD + B[i]) % MOD;
        if (i != 0) {
            a_m = (a_m * D) % MOD;
        }
    }


    memset(match, 0, sizeof (bool) * MAXN);
    int count = 0;
    for (int i = 0; i <= n - m - 1; i++) {
        if (hashA == hashB_m) {
            if (A.compare(B.substr(i, m)) == 0) {
                match[i] = true;
                count++;
            }
        }
        if (i + m < n)
            hashB_m = (((hashB_m - (a_m * B[i]) % MOD + MOD) * D) % MOD + B[i + m]) % MOD;
    }
    cout << count << endl;
    int nrRes = min((int) count, 1000);
    for (int i = 0; i < MAXN || nrRes > 0; i++) {
        if (match[i]) {
            cout << i<< " ";
            nrRes --;
        }
    }
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    string A, B;
    cin >> A >> B;
    rabinKarpMatch(A, B);
    fclose(stdin);
    fclose(stdout);
}