Cod sursa(job #2284623)

Utilizator Mathe13Mathe Andrei Mathe13 Data 17 noiembrie 2018 12:01:31
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <math.h>

using namespace std;

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

char A[2000045], B[2000045];
int n = 3, m = 20000001, hashA = 0, hashB = 0, sol = 0;
int pos[2000045];

int meMario(int nr, int put)
{
    int result = 1;
    for (int i = 0; i < put; ++i)
        result *= nr;
    return result;
}

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

int Niext(int hashul, int position, int len)
{
    hashul -= (B[position-1] * meMario(n, len-1));
    hashul *= n;
    hashul += B[position+2];
    hashul %= m;
    return hashul;
}

void Solve()
{
    int a_len = strlen(A);
    int oh = 0;
    hashA = Hash(A, n, m, hashA, a_len);

    char str[a_len];
    for (int i = 0; i < a_len; ++i)
        str[i] = B[i];
    int hashul = 0;
    hashul = Hash(str, n, m, hashul, a_len);

    if (hashA == hashul){
        ++sol;
        pos[oh] = 0;
        ++oh;
    }

    for (int i = 1; i <= strlen(B) - a_len; ++i){
        hashul = Niext(hashul, i, a_len);

        if (hashA == hashul){
            ++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;
}