Cod sursa(job #1193136)

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

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

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; 
        }
    }
    
    vector<int> match; 
    
    for (int i = 0; i <= n - m  - 1; i++) {
        if (hashA == hashB_m) {
            if (A.compare(B.substr(i, m)) == 0) {
                match.push_back(i); 
            }
        }
        if (i + m < n)
            hashB_m = (((hashB_m - (a_m * B[i]) % MOD + MOD) * D) % MOD + B[i + m] ) % MOD;
    }
    cout << match.size() << endl; 
    int nrRes = min((int)match.size(), 1000); 
    for (int i = 0; i < nrRes; i++) {
        cout << match[i] << " ";
    }
}

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); 
}