Cod sursa(job #2284349)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 17 noiembrie 2018 10:41:00
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <cstdio>
#include <string.h>
using namespace std;

char s1[2000005];
char s2[2000005];
long long a[1005];
long long l1, l2;
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", s1, s2);
    l1=strlen(s1);
    l2=strlen(s2);
    Hash pHash{31,1046527},tHash{31,1046527};
    Hash hHash{53,177777},oHash{53,177777};
    long long nr=0;
    pHash.init(s1,l1);
    tHash.init(s2,l1);
    hHash.init(s1,l1);
    oHash.init(s2,l1);
    if(pHash.hashh==tHash.hashh && hHash.hashh==oHash.hashh)
    {
        a[nr++]=0;
    }
     for(int i=l1;i<l2;i++)
    {
        tHash.roll(s2[i-l1],s2[i]);
        oHash.roll(s2[i-l1],s2[i]);
        if(tHash.hashh==pHash.hashh && hHash.hashh==oHash.hashh)
        {
            if(nr<1000)
                a[nr++]=(i-l1+1);
            else nr++;
        }
    }
    printf("%d\n",nr);
    if(nr<1000)
    {
        for(int i=0; i<nr; i++)
            printf("%d ", a[i]);
    }
    else
    {
        for(int i=0; i<1000;i++)
            printf("%d",a[i]);
    }
    return 0;
}