Cod sursa(job #1193145)

Utilizator lvamanuLoredana Vamanu lvamanu Data 31 mai 2014 01:19:09
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 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;

vector<int> match;

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;
        }
    }
    int count = 0;
    for (int i = 0; i <= n - m ; 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;
    }
    printf("%d\n",match.size());
    int nrRes = min((int) match.size(), 1000);
    for (int i = 0; i < nrRes; i++) {
        printf("%d ", 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);
}