Cod sursa(job #2028070)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 27 septembrie 2017 09:23:13
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <bits/stdc++.h>

using namespace std;

char a[2000005];
char b[2000005];
int  d[2000005];
int nrsol = -1, sol[1000];
int la, lb;

void precalc()
{
    int q = -1;
    d[0] = -1;
    for(int i = 1; i < la; i++)
    {
        while(q != -1 && a[q + 1] != a[i])
            q = d[q];
        if(a[q + 1] == a[i])
            q++;
        d[i] = q;
    }
}

void kmp()
{
    precalc();
    int q = -1;
    for(int i = 0; i < lb; i++)
    {
        while(q != -1 && b[i] != a[q + 1])
            q = d[q];
        if(b[i] == a[q + 1])
            q++;
        if(q == la - 1)
        {
            ++nrsol;
            if(nrsol < 1000)
                sol[nrsol] = i - la + 1;
            q = d[q];
        }
    }
}

void rabin()
{
    const unsigned int k1 = 33, k2 = 31;
    unsigned int ha1 = 0, ha2 = 0, pk1 = 1, pk2 = 1, hb1 = 0, hb2 = 0;
    for(int i = 0; i < la; i++)
    {
        ha1 = ha1 * k1 + a[i];
        ha2 = ha2 * k2 + a[i];
        hb1 = hb1 * k1 + b[i];
        hb2 = hb2 * k2 + b[i];
    }
    for(int i = 1; i < la; i++)
    {
        pk1 = pk1 * k1;
        pk2 = pk2 * k2;
    }
    if(ha1 == hb1 && ha2 == hb2)
    {
        ++nrsol;
        if(nrsol < 1000)
            sol[nrsol] = 1;
    }
    for(int i = la; i < lb; i++)
    {
        hb1 = hb1 - pk1 * b[i - la];
        hb2 = hb2 - pk2 * b[i - la];
        hb1 = hb1 * k1 + b[i];
        hb2 = hb2 * k2 + b[i];
        if(ha1 == hb1 && ha2 == hb2)
        {
            ++nrsol;
            if(nrsol < 1000)
                sol[nrsol] = i - la + 1;
        }
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s%s", a, b);
    la = strlen(a);
    lb = strlen(b);
    rabin();
    nrsol++;
    printf("%d\n", nrsol);
    int k = min(1000, nrsol);
    for(int i = 0; i < k; i++)
        printf("%d ", sol[i]);
    return 0;
}