Cod sursa(job #2284341)

Utilizator cristina-criCristina cristina-cri Data 17 noiembrie 2018 10:37:26
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <cstring>

#define NMAX 2000005


using namespace std;

char p[NMAX], t[NMAX];
long long n, m, nr, a[1005];

struct Hash
{
    long long n, m, power, hashh;

    void init(char *s, long long len)
    {
        power=1;
        hashh=0;
        for(long long i=len-1; i>=0; i--)
        {
            hashh=(hashh+1LL*power*s[i])%m;
            if(i)
                power=(power*n)%m;
        }
    }

    void roll(char toRemove, char toAdd)
    {
        hashh=(((hashh-1LL*toRemove*power+m)*n)%m+toAdd)%m;
    }

};

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n%s", p, t);

    n=strlen(p);
    m=strlen(t);

    Hash pHash{3, 1046527}, tHash{3, 1046527};
    Hash hHash{5, 42589}, oHash{5, 42589};
    pHash.init(p, n);
    tHash.init(t, n);
    hHash.init(p, n);
    oHash.init(t, n);

    if(pHash.hashh == tHash.hashh && hHash.hashh == oHash.hashh)
        a[++nr]=0;
    for(long long i=n; i<m; i++)
    {
        tHash.roll(t[i-n], t[i]);
        oHash.roll(t[i-n], t[i]);
        if(pHash.hashh == tHash.hashh && hHash.hashh == oHash.hashh)
        {
            if(nr<=1000)
                a[++nr]=(i-n+1);
            else
                nr++;
        }
    }
    printf("%lld\n", nr);
    if(nr>1000)
        nr=1000;
    for(int i=1; i<=nr; i++)
    {
        printf("%lld ", a[i]);
    }
    return 0;
}