Cod sursa(job #2284471)

Utilizator Mathe13Mathe Andrei Mathe13 Data 17 noiembrie 2018 11:10:19
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <cstring>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char A[2000045], B[2000045];
int n1 = 3, m1 = 200001, n2 = 5, m2 = 2000001, hashA = 0, hashB = 0, sol = 0;
int pos[2000045];

int Hash(char str[], int n, int m, int hashul, int len)
{
    for (int i = 0; i < len; ++i){
        hashul *= n1;
        hashul += str[i];
    }
    hashul = hashul%m;
    return hashul;
}

void Solve()
{
    int a_len = strlen(A);
    int b_len = strlen(B);
    hashA = Hash(A, n1, m1, hashA, a_len);
    hashB = Hash(B, n2, m2, hashB, b_len);

    for (int i = 0, oh = 0; i < strlen(B) - a_len; ++i){
        char str[a_len];
        for (int j = i, k = 0; j < i + a_len; ++j, ++k)
            str[k] = B[j];
        int hasul = 0;
        hasul = Hash(str, n1, m1, hasul, strlen(str));

        if (hashA == hasul){
            ++sol;
            pos[oh] = i;
            ++oh;
        }
    }
}

void Read()
{
    fin.getline(A, 2000045);
    fin.getline(B, 2000045);
}

void Write()
{
    fout << sol << "\n";
    for (int i = 0; i < sol; ++i)
        fout << pos[i] << " ";
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}