Cod sursa(job #1955306)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 5 aprilie 2017 21:41:16
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 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];
bool fol[2000005];
int n, m, i, j;
int Hash1, Hash2, P1, P2;
int HashB1, HashB2, ns;

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

    P1 = P2 = 1;
    for (i = 1; 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>1) P1 = (P1*P)%mod1, P2 = (P2*P)%mod2;
    }
    if (n > m) {
        g<<0;
        return 0;
    }

    if (HashB1==Hash1 && HashB2==Hash2) fol[0] = 1, ns++;
    for (i = n+1; 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[i-n] = 1, ns++;
    }

    g << ns << '\n';
    ns = 0;
    for (i = 0; i < m && ns <= 1000; i++)
        if (fol[i]) {
            g << i << ' ';
            ns++;
        }
    return 0;
}