Cod sursa(job #1134260)

Utilizator andreiagAndrei Galusca andreiag Data 6 martie 2014 12:07:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <string>
#include <fstream>
#include <stdio.h>

using namespace std;

const int P = 101;

const int MOD1 = 31627;
const int MOD2 = 31013;

int match[1005];

int main()
{
    ifstream f ("strmatch.in");
    ofstream g ("strmatch.out");

    string A, B;

    getline(f, A);
    getline(f, B);

    int NA = A.size(), NB = B.size();

    int hash1 = 0, hash2 = 0, P1 = 1, P2 = 1;
    
    for (int i = 0; i < NA; i++)
    {
        hash1 = (hash1 * P + A[i]) % MOD1;
        hash2 = (hash2 * P + A[i]) % MOD2;

        P1 = (P1 * P) % MOD1;
        P2 = (P2 * P) % MOD2;
    }

    if (NA > NB) {
        g << 0 << endl;
        return 0;
    }

    int H1 = 0, H2 = 0;
    for (int i = 0; i < NA; i++) {
        H1 = (H1 *P + B[i]) % MOD1;
        H2 = (H2 *P + B[i]) % MOD2;
    }
    
    int cnt = 0;
    if (hash1 == H1 && hash2 == H2) {
        cnt++; match[0] = 0;
    }

    for (int i = NA; i < NB; i++) {
        H1 = (H1*P + B[i] - P1*B[i-NA]) % MOD1;
        if (H1 < 0) H1 += MOD1;

        H2 = (H2*P + B[i] - P2*B[i-NA]) % MOD2;
        if (H2 < 0) H2 += MOD2;
        
        if (hash1 == H1 && hash2 == H2) {
            if (cnt < 1000) match[cnt] = i-NA+1;
            cnt++;
        }
    }
    g << cnt << '\n';
    for (int i = 0; i < 1000 && i < cnt; i++)
        g << match[i] << ' ';
    g << endl;

    return 0;
}