Cod sursa(job #311590)

Utilizator sandyxpSanduleac Dan sandyxp Data 3 mai 2009 18:56:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <string>
#include <iterator>
#include <vector>
#include <cmath>
using namespace std;

#define NUME "strmatch"
ifstream fi(NUME".in");
ofstream fo(NUME".out");

#define P1 100007
#define P2 100021
// maybe better to be larger than values ( > 'z')
// FIXME: cat mai departe de o putere a lui 2 ?
// 293, 307
#define X 67
#define hash1(crt, x) (crt*X + x) % P1
#define hash2(crt, x) (crt*X + x) % P2
#define MAXN 100001

vector<int> occ;
string A, B;

int main()
{
    occ.reserve(1000);
    int i, j, k, M;
    int ptn1 = 0, ptn2 = 0; // hash pt pattern
    int power1 = 1, power2 = 1;
    int h1 = 0, h2 = 0, nr = 0;
    fi >> B >> A;
    M = B.size();
    for (i = 0; i < M; ++i) {
        ptn1 = hash1(ptn1, B[i]), ptn2 = hash2(ptn2, B[i]);
        if (!i) continue;
        power1 = (power1 * X) % P1;
        power2 = (power2 * X) % P2;
    }
    for (i = 0; i < A.size(); ++i) {
        if (i >= M) {
            h1 = h1 - (A[i-M] * power1) % P1 + P1;
            h2 = h2 - (A[i-M] * power2) % P2 + P2;
        }
        h1 = hash1(h1, A[i]);
        h2 = hash2(h2, A[i]);
        if (i < M-1) continue;
        if (h1 == ptn1 && h2 == ptn2) {
            nr ++;
            if (occ.size() < 1000)
                occ.push_back(i-M+1);
        }
    }
    fo << nr << "\n";
    copy(occ.begin(), occ.end(), ostream_iterator<int>(fo, " "));
    return 0;
}