Cod sursa(job #1955348)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 5 aprilie 2017 22:02:52
Problema Potrivirea sirurilor Scor 92
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
// RABIN-KARP
// Made in Romania by Florin Haja

#include <bits/stdc++.h>

using namespace std;

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

const int mod1 = 100007, mod2 = 100021, P = 73;
char a[2000005], b[2000005];
int fol[2000005];
int n, m, i, j;
int Hash1, Hash2, P1, P2;
int HashB1, HashB2, ns;

int main() {
    f.getline(a, sizeof(a));
    f.getline(b, sizeof(b));
    n = strlen(a), m = strlen(b);
    for (i = 0; i < n; i++)
        a[i] -= 'A';
    for (i = 0; i < m; i++)
        b[i] -= 'A';

    P1 = P2 = 1;
    for (i = 0; i < n; i++) {
        Hash1 = (Hash1 * P + a[i])%mod1;
        Hash2 = (Hash2 * P + a[i])%mod2;
        HashB1 = (HashB1 * P + b[i])%mod1;
        HashB2 = (HashB2 * P + b[i])%mod2;

        if (i) P1 = (P1*P)%mod1, P2 = (P2*P)%mod2;
    }
    if (n > m) {
        g<<0;
        return 0;
    }

    if (HashB1==Hash1 && HashB2==Hash2) fol[ns=1] = 0;

    for (i = n; i < m; i++) {
        HashB1 = ((( (HashB1 - b[i-n]*P1)%mod1 )+mod1 ) * P + b[i] ) %mod1;
        HashB2 = ((( (HashB2 - b[i-n]*P2)%mod2 )+mod2 ) * P + b[i] ) %mod2;
        if (HashB1==Hash1 && HashB2==Hash2) fol[++ns] = i-n+1;
    }

    g << ns << '\n';
    for (i = 1; i <= min(ns,1000); i++)
        g<<fol[i] << ' ';
    return 0;
}