Cod sursa(job #311585)

Utilizator sandyxpSanduleac Dan sandyxp Data 3 mai 2009 18:51:55
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 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 okay(x, prim) ((x) + prim) % prim

//int H1[P][4], H2[P][4], nr1[P], nr2[P];
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) {
            int lim = (int)sqrt(M);
            for (j = i-M+1, k = 0; k < M; j++, k ++)
                if (A[j] != B[k]) break;
            if (k == M) {
                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;
}