Cod sursa(job #2337315)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 6 februarie 2019 11:40:09
Problema Potrivirea sirurilor Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <cstring>
using namespace std;

char a[100],b[100];

struct Hash{
    int 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)%m;
            if(i)
                power=(power*n)%m;
        }
    }

    void roll(char toAdd, char toRemove){

        hashh=(((hashh-(1LL*toRemove*power)%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 pHash{31,40099},tHash{31,40099};
    Hash oHash{53,319993}, hHash{53,319993};
    int nr=0;

    int afis[100];
    pHash.init(a,l1);
    tHash.init(b,l1);
    oHash.init(a,l1);
    hHash.init(b,l1);

    if(pHash.hashh==tHash.hashh && oHash.hashh==hHash.hashh)
        afis[++nr]=0;

    for(int i=l1; i<l2;i++){

        tHash.roll(b[i],b[i-l1]);
        hHash.roll(b[i],b[i-l1]);
        if(pHash.hashh==tHash.hashh && oHash.hashh==hHash.hashh)
            afis[++nr]=i-l1+1;
    }

    printf("%d\n",nr);
    for(int i=1; i<=nr; i++)
        printf("%d ",afis[i]);
    return 0;
}