Cod sursa(job #1273982)

Utilizator andreiagAndrei Galusca andreiag Data 23 noiembrie 2014 02:52:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
// rabin-karp
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;
const int Nmax = 2000666;

string A, B;
const int P = 101;
const int mod1 = 1000003;
const int mod2 = 1000033;
int sol[1033];

int main()
{
    ifstream f ("strmatch.in");
    ofstream g ("strmatch.out");
    
    f >> A >> B;
    int M = A.length(), N = B.length();
    
    if (M > N) {
        g << 0 << '\n';
        return 0;
    }
    B.push_back('_');
    
    int hash1 = A[0], hash2 = A[0];
    int HB1 = B[0], HB2 = B[0];
    int P1 = 1, P2 = 1;
    
    for (int i = 1; i < M; i++) {
        hash1 = (hash1 * P + A[i]) % mod1;
        hash2 = (hash2 * P + A[i]) % mod2;

        HB1 = (HB1 * P + B[i]) % mod1;
        HB2 = (HB2 * P + B[i]) % mod2;

        P1 = (P1 * P) % mod1;
        P2 = (P2 * P) % mod2;
    }
    
    int start = 0, i = M;
    int answer = 0;
    do {
        if ((HB1 == hash1) && (HB2 == hash2)) { // match
            answer++;
            if (answer < 1000)
                sol[answer] = start;
        }

        HB1 = (((HB1 - (B[start]*P1) % mod1 + mod1) * P) + B[i]) % mod1;
        HB2 = (((HB2 - (B[start]*P2) % mod2 + mod2) * P) + B[i]) % mod2;

        start++;
        i++;
    } while (i <= N);

    g << answer << '\n';
    for (int j = 1; (j <= answer) && (j <= 1000); j++) {
        g << sol[j] << ' ';
    }
    if (answer)
        g << '\n';

    return 0;
}