Cod sursa(job #2678288)

Utilizator teomarsTeodora Sintea teomars Data 28 noiembrie 2020 11:38:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <cstring>
#include <cstdio>
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021

using namespace std;

char a[MAXN], b[MAXN];
int n, m, nr;
int hash1, hash2, p1, p2, h1, h2;
char match[MAXN];

void citire()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n %s", a, b);
    n=strlen(a);
    m=strlen(b);
}

void comparare()
{
    p1=p2=1;
    hash1=hash2=0;
    for (int i=0;i<n;i++)
    {
        hash1 = (hash1 * P + a[i]) % MOD1;
        hash2 = (hash2 * P + a[i]) % MOD2;
        if (i != 0)
            p1 = (p1 * P) % MOD1,
            p2 = (p2 * P) % MOD2;
    }
    for (int i = 0; i < n; i++)
        h1 = (h1 * P + b[i]) % MOD1,
        h2 = (h2 * P + b[i]) % MOD2;
    if (h1 == hash1 && h2 == hash2)
        match[0] = 1, nr++;
    for (int i = n; i < m; i++)
    {
        h1 = ((h1 - (b[i - n] * p1) % MOD1 + MOD1) * P + b[i]) % MOD1;
        h2 = ((h2 - (b[i - n] * p2) % MOD2 + MOD2) * P + b[i]) % MOD2;
        if (h1 == hash1 && h2 == hash2)
            match[ i - n + 1 ] = 1, nr++;
    }
}

void afisare()
{
    cout<<nr<<'\n';
    nr = 0;
    for (int i = 0; i < m && nr < 1000; i++)
        if (match[i])
        {
            nr++;
            cout<<i<<' ';
        }
}

int main()
{
    citire();
    if (n > m)
    {
        cout<<0;
        return 0;
    }
    comparare();
    afisare();
    return 0;
}