Cod sursa(job #2287753)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 22 noiembrie 2018 14:25:46
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <cstdio>
#include <string.h>

using namespace std;

char a[2000001], b[2000001];
int c[1002], o;


struct Hash{
    int n, m;
    long long p=1, rez=0;
    long long h1(char *a, int l)
    {
        p = 1;
        rez=0;
        for(int i=l-1; i>=0; i--)
        {
            rez = (rez + (a[i]*p)%m)%m;
            p = (p * n)%m;
        }
        p/=n;
        return rez;
    }
    void roll(char toRemove, char toAdd)
    {
        rez=(((rez-(1LL*toRemove*p)%m+m)*n)%m+toAdd)%m;
    }

};




int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n%s", a, b);
    int l1 = strlen(a), l2 = strlen(b);
    Hash tc1, tc2;
    Hash c1, c2;

    tc1.n = 31;
    tc1.m = 40099;
    c1.n = 31;
    c1.m = 40099;

    tc2.n = 53;
    tc2.m = 319993;
    c2.n = 53;
    c2.m = 319993;


    tc1.h1(a, l1);
    tc2.h1(a, l1);
    c1.h1(b, l1);
    c2.h1(b, l1);

    if(tc1.rez == c1.rez && tc2.rez == c2.rez)
    {
        c[o++] = 0;
    }
    for(int i=l1; i<l2; i++)
    {
        c1.roll(b[i-l1], b[i]);
        c2.roll(b[i-l1], b[i]);
        if(tc1.rez == c1.rez && tc2.rez == c2.rez)
        {
            if(o < 1000)
                c[o] = i-l1+1;
            o++;
        }
    }
    printf("%d\n", o);
    if(o > 999)
        for(int i=0; i<1000; i++)
            printf("%d ", c[i]);
    else for(int i=0; i<o; i++)
        printf("%d ", c[i]);

    return 0;
}