Cod sursa(job #2353126)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 23 februarie 2019 21:37:01
Problema Potrivirea sirurilor Scor 92
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstring>
#include <fstream>

#define BASE 73
#define MOD1 100007
#define MOD2 100021

#define MAX 1000
#define SMAX 2000010

std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");

int m; char a[SMAX];
int n; char b[SMAX];

int nrSol;
int sol[SMAX];

int main() {
    fin >> a; m = strlen(a);
    fin >> b; n = strlen(b);

    int hash01 = 0, hash1 = 0, power1 = 1;
    int hash02 = 0, hash2 = 0, power2 = 1;

    for (int i = 0; i < m; i++) {
        hash01 = (hash01 * BASE + a[i] - 'A' + 1) % MOD1;
        hash02 = (hash02 * BASE + a[i] - 'A' + 1) % MOD2;

        hash1 = (hash1 * BASE + b[i] - 'A' + 1) % MOD1;
        hash2 = (hash2 * BASE + b[i] - 'A' + 1) % MOD2;
    }

    for (int i = 1; i < m; i++) {
        power1 = power1 * BASE % MOD1;
        power2 = power2 * BASE % MOD2;
    }

    if (hash1 == hash01 && hash2 == hash02)
        sol[nrSol++] = 0;

    for (int i = m; i < n; i++) {
        hash1 = ((hash1 - (b[i - m] - 'A' + 1) * power1 % MOD1 + MOD1) * BASE + b[i] - 'A' + 1) % MOD1;
		hash2 = ((hash2 - (b[i - m] - 'A' + 1) * power2 % MOD2 + MOD2) * BASE + b[i] - 'A' + 1) % MOD2;

        if (hash1 == hash01 && hash2 == hash02)
            sol[nrSol++] = i - m + 1;
    }

    fout << nrSol << '\n';
    for (int i = 0; i < nrSol && i < MAX; i++)
        fout << sol[i] << ' ';
    fout << '\n';

    fout.close();
    return 0;
}