Cod sursa(job #1562026)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 4 ianuarie 2016 19:04:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 2000050

using namespace std;

char A[MAXN], B[MAXN];
const int base1 = 131, base2 = 137, mod1 = 100003, mod2 = 100019;
int n, m, sol[1050];

//    for (int i = 0; i < n; i++) {
//		hashA1 = (hashA1 + A[i]*fact1) % mod1;
//		hashA2 = (hashA2 + A[i]*fact2) % mod2;
//		fact1 *= base1;
//		fact2 *= base2;
//    }

int getHash(char *S, int len, int &fact, int base, int mod)
{
	int h = 0;
	fact = 1;
    for (int i = len-1; i; --i) {
		h = (h + *(S+i) * fact) % mod;
		fact = (fact * base) % mod;
    }
    h = (h + *S * fact) % mod;
    return h;
}

void solve()
{
    int fact1, fact2;
    int hashA1, hashA2, hashB1, hashB2;
    n = strlen(A); m = strlen(B);
    if (n > m) {
		printf("0");
		return ;
    }
    hashA1 = getHash(A, n, fact1, base1, mod1);
    hashA2 = getHash(A, n, fact2, base2, mod2);
    hashB1 = getHash(B, n, fact1, base1, mod1);
    hashB2 = getHash(B, n, fact2, base2, mod2);

	if (hashA1 == hashB1 && hashA2 == hashB2)
		sol[(++sol[0]) > 1000 ? 1001 : sol[0]] = 0;

	for (int i = n; i < m; i++) {
        hashB1 = (((hashB1 - fact1*B[i-n] + 128*mod1)%mod1)*base1 + B[i])%mod1;
		hashB2 = (((hashB2 - fact2*B[i-n] + 128*mod2)%mod2)*base2 + B[i])%mod2;

        if (hashA1 == hashB1 && hashA2 == hashB2)
            sol[(++sol[0]) > 1000 ? 1001 : sol[0]] = i-n+1;
    }
    printf("%d\n", sol[0]);
    for (int i = 1; i <= sol[0]; i++)
		printf("%d ", sol[i]);
	/// debug: printf("%d %d\n%d %d", hashA1, hashA2, hashB1, hashB2);
}

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

    gets(A);
    gets(B);
    solve();

    return 0;
}