Cod sursa(job #1484268)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 10 septembrie 2015 18:06:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>

#define INF ( (1 << 30) - 1 + (1 << 30) )
#define mod 666013

#define b1 127
#define b2 131
#define mod1 1000000007
#define mod2 1000000021

using namespace std;

int n, m, i, j, h1, h2, H1, H2;
int q, r[1005];
int hsh1[2000005], hsh2[2000005], p1[2000005], p2[2000005];
char a[2000005], b[2000005];

int HASH1(int st, int dr)
{
    int rez = hsh1[dr];
    int x = (1LL * hsh1[st - 1] * p1[dr - st + 1]) % mod1;
    rez -=  x;
    if(rez < 0)
        rez += mod1;
    return rez;
}

int HASH2(int st, int dr)
{
    int rez = hsh2[dr];
    int x = (1LL * hsh2[st - 1] * p2[dr - st + 1]) % mod2;
    rez -=  x;
    if(rez < 0)
        rez += mod2;
    return rez;
}

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);

    p1[0] = p2[0] = 1;
    for(i = 1; i <= m; i++)
    {
        p1[i] = (1LL * p1[i - 1] * b1) % mod1;
        p2[i] = (1LL * p2[i - 1] * b2) % mod2;

        hsh1[i] = (1LL * hsh1[i - 1] * b1) % mod1;
        hsh1[i] = (hsh1[i] + b[i]) % mod1;

        hsh2[i] = (1LL * hsh2[i - 1] * b2) % mod2;
        hsh2[i] = (hsh2[i] + b[i]) % mod2;
    }

    H1 = H2 = 0;
    for(i = 1; i <= n; i++)
    {
        H1 = (1LL * H1 * b1) % mod1;
        H1 = (H1 + a[i]) % mod1;

        H2 = (1LL * H2 * b2) % mod2;
        H2 = (H2 + a[i]) % mod2;
    }

    for(i = 1; i <= m - n + 1; i++)
    {
        h1 = HASH1(i, i + n - 1);
        h2 = HASH2(i, i + n - 1);
        if(H1 == h1 && H2 == h2)
        {
            q++;
            if(q <= 1000)
                r[q] = i - 1;
        }
    }

    printf("%d\n", q);
    for(i = 1; i <= q; i++)
        printf("%d ", r[i]);

    return 0;
}