Cod sursa(job #2063564)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 11 noiembrie 2017 12:07:21
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define NMAX 2000005
#define MOD 101

using namespace std;

char p[NMAX], s[NMAX];
int hashSol, hashSecv, P = 256, putere = 1, sol[1005];

void hashFunction()
{
    int n = strlen(p);
    hashSol = p[0] % MOD;
    hashSecv = s[0] % MOD;
    for(int i=1; i<n; ++i)
    {
        hashSol = ((hashSol * P) % MOD + p[i]) % MOD;
        hashSecv = (hashSecv * P + s[i]) % MOD;
        putere = (putere * P) % MOD;
    }
}

void cautareNaiva(int poz)
{
    int n = strlen(p);
    for(int i=poz, k = 0; i<poz + n; ++i, ++k)
        if(p[k] != s[i])
            return;
    if(sol[0] < 1000)
        sol[++sol[0]] = poz - n + 1;
}

void solve()
{
    if(hashSol == hashSecv)
        cautareNaiva(0);

    int n = strlen(s), m = strlen(p);

    for(int i = m; i<n; ++i)
    {
        hashSecv = (((hashSecv - (s[i - m]*putere) % MOD + MOD) % MOD * P)% MOD + s[i]) % MOD;
        if(hashSecv == hashSol)
            cautareNaiva(i);
    }
}

void print()
{
    printf("%d\n", hashSol);

    for(int i=1; i<=sol[0]; ++i)
        printf("%d ", sol[i]);
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    //freopen("strmatch.out", "w", stdout);

    scanf("%s\n%s", &p, &s);

    hashFunction();
    solve();
    print();
    return 0;
}