Cod sursa(job #1871513)

Utilizator SilviuIIon Silviu SilviuI Data 7 februarie 2017 14:26:11
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <stdio.h>
#include <cstring>
#include <vector>
#define nmax 2000010
#define mod1 666013
#define mod2 666019
#define P 256

using namespace std;

struct hashFunction {
    int hash1, hash2;
};

int n, m, nr;
hashFunction p, hashF, currentHash;
char a[nmax], b[nmax];

vector <int> ans;

bool operator==(hashFunction hash1, hashFunction hash2)
{
    return (hash1.hash1 == hash2.hash1 && hash1.hash2 == hash2.hash2);
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    gets(a + 1); n = strlen(a + 1);
    gets(b + 1); m = strlen(b + 1);

    hashF.hash1 = 0;
    hashF.hash2 = 0;

    for (int i = 1; i <= n; i++) {
        hashF.hash1 = (1LL * hashF.hash1 * P + a[i]) % mod1;
        hashF.hash2 = (1LL * hashF.hash2 * P + a[i]) % mod2;
    }

    currentHash.hash1 = 0;
    currentHash.hash2 = 0;

    p.hash1 = 1; p.hash2 = 1;

    for (int i = 1; i <= n; i++) {
        currentHash.hash1 = (1LL * currentHash.hash1 * P + b[i]) % mod1;
        currentHash.hash2 = (1LL * currentHash.hash2 * P + b[i]) % mod2;

        if (i > 1) {
            p.hash1 = (1LL * p.hash1 * P) % mod1;
            p.hash2 = (1LL * p.hash2 * P) % mod2;
        }
    }

    if (currentHash == hashF) { nr = 1; ans.push_back(0); } else
        nr = 0;

    for (int i = n + 1; i <= m; i++) {

        currentHash.hash1 = (currentHash.hash1 - (1LL * b[i - n] * p.hash1) % mod1);
        currentHash.hash2 = (currentHash.hash2 - (1LL * b[i - n] * p.hash2) % mod2);

        if (currentHash.hash1 < 0) currentHash.hash1 += mod1;
        if (currentHash.hash2 < 0) currentHash.hash2 += mod2;

        currentHash.hash1 = (1LL * currentHash.hash1 * P + b[i]) % mod1;
        currentHash.hash2 = (1LL * currentHash.hash2 * P + b[i]) % mod2;

        if (currentHash == hashF) {

            nr++;

            if (ans.size() < 1000) ans.push_back(i - n);
        }

    }

    printf("%d\n", nr);

    for (int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);

    return 0;
}