Cod sursa(job #2675194)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 21 noiembrie 2020 11:04:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#define NMAX 2000005
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long lli;
char s1[NMAX], s2[NMAX];
lli a[1005];
lli l1, l2, nr;


class Hash{
    private:
        lli n, m, power, value;
    public:
        Hash(){n = 0, m = 0, power = 0, value = 0;}
        Hash(int nn, int mm) {n = nn; m = mm;}

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

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

        void Val()
        {
            printf("{%lld %lld %lld %lld}", n, m, power, value);
        }

        bool operator==(const Hash &other) const {
            return value == other.value;
        }

};

void read()
{
    scanf("%s\n%s", s1, s2);
    l1 = strlen(s1);
    l2 = strlen(s2);
}


void solve()
{
    Hash shor[2]{{31, 40099}, {53, 319993}};
    Hash lo[2]{{31, 40099}, {53, 319993}};

    for(int i = 0; i < 2; ++i)
    {
        shor[i].init(s1, l1);
        lo[i].init(s2, l1);
    }

    if(shor[0] == lo[0] && shor[1] == lo[1])
        a[++nr] = 0;
    for(int i = l1; i < l2; ++i)
    {
        for(int k = 0; k < 2; ++k)
            lo[k].roll(s2[i-l1], s2[i]);
        if(shor[0] == lo[0] && shor[1] == lo[1])
        {
            if(nr <= 1000)
                a[++nr] = i-l1+1;
            else nr++;
        }
    }
}



void write()
{
    int vmin = (nr >= 1000)?1000:nr;
    printf("%d\n", nr);
    for(int i = 1; i <= vmin; ++i)
        printf("%d ", a[i]);
}


int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    read();
    solve();
    write();
    return 0;
}