Cod sursa(job #1005189)

Utilizator gabrieligabrieli gabrieli Data 4 octombrie 2013 14:54:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");

    string A, B;
    int P(263), P1(1), P2(1),
        hashA1(0), hashA2(0),
        hashB1(0), hashB2(0),
        mod1(100003), mod2(100019),
        matches[1001], nr(0);

    getline(fin, A);
    getline(fin, B);

    if (A.size() > B.size()) {
        fout << '0' << endl;
        return 0;
    }

    for (size_t i = 0; i < A.size(); ++i) {
        hashA1 = (hashA1 * P + A[i]) % mod1;
        hashA2 = (hashA2 * P + A[i]) % mod2;
    }
    for (size_t i = 0; i < A.size(); ++i) {
        hashB1 = (hashB1 * P + B[i]) % mod1;
        hashB2 = (hashB2 * P + B[i]) % mod2;
        if (i != 0) {
            P1 = (P1 * P) % mod1;
            P2 = (P2 * P) % mod2;
        }
    }

    if (hashA1 == hashB1 && hashA2 == hashB2)
        matches[nr++] = 0;

    for (size_t i = A.size(); i < B.size(); ++i) {
        hashB1 = (((hashB1 - B[i-A.size()] * P1) % mod1 + mod1) * P + B[i]) % mod1;
        hashB2 = (((hashB2 - B[i-A.size()] * P2) % mod2 + mod2) * P + B[i]) % mod2;

        if (nr < 1000 && hashA1 == hashB1 && hashA2 == hashB2)
            matches[nr++] = i - A.size() + 1;
        else if(hashA1 == hashB1 && hashA2 == hashB2)
            nr++;
    }

    fout << nr << '\n';
    for (int i = 0; i < nr && i < 1000; ++i)
        fout << matches[i] << ' ' ;
    fout << endl;

    return 0;
}