Cod sursa(job #2284336)

Utilizator razvanradulescuRadulescu Razvan razvanradulescu Data 17 noiembrie 2018 10:36:44
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;

const long long n1 = 31, m1 = 6221, n2 = 53, m2 = 42589;
long long nrAp, hashInit1, hashInit2;
char a[2000005], b[2000005];
int v[1005];
long long nrLaPut = 1;

int RabinKarp(char s[2000000], int k, int n, int m)
{
    long long nr = 0;
    for(int i = 0; i<k; i++)
    {
        nr=(nr*n)%m;
        nr=(nr+s[i])%m;
        if(i != 0)
            nrLaPut=(nrLaPut*n)%m;
    }
    return nr;
}

void rez()
{
    long long put1, put2;
    scanf("%s", a);
    scanf("%s", b);
    int la = strlen(a), lb = strlen(b);
    hashInit1 = RabinKarp(a, la, n1, m1);
    put1 = nrLaPut;
    nrLaPut = 1;
    hashInit2 = RabinKarp(a, la, n2, m2);
    put2 = nrLaPut;
    nrLaPut = 1;
    long long hash2, hash1;
    hash1 = RabinKarp(b, la, n1, m1);
    nrLaPut = 1;
    hash2 = RabinKarp(b, la, n2, m2);
    if(hash1 == hashInit1 && hash2 == hashInit2)
    {
        v[nrAp] = 0;
        nrAp++;
    }
    for(int i = 1; i<lb-la+1; i++)
    {
        hash1 = ((hash1-(b[i-1]*put1)%m1+m1)*n1 + b[i+la-1])%m1;
        hash2 = ((hash2-(b[i-1]*put2)%m2+m2)*n2 + b[i+la-1])%m2;
        if(hash1 == hashInit1 && hash2 == hashInit2)
        {
            v[nrAp] = i;
            nrAp++;
        }
    }
    printf("%lld\n", nrAp);
    for(int i = 0; i<nrAp && i<1000; i++)
    {
        printf("%d ", v[i]);
    }
}

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