Cod sursa(job #2409722)

Utilizator osiaccrCristian Osiac osiaccr Data 19 aprilie 2019 12:53:28
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define DEF 2000010
#define MODO 666013

using namespace std;

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

int lenA, lenB, hashA, hashB, pow256 = 1, sol;

vector < int > Pos;

char A[DEF], B[DEF];

int create_hash (char a[], int len) {
    int _hash = a[0] % MODO;
    for (int i = 1; i < len; ++ i) {
        _hash = ((1LL * _hash * 256) % MODO + a[i]) % MODO;
    }
    return _hash;
}

int roll_hash (int _hash, char to_rem, char to_add) {
    _hash = (1LL * ((_hash + MODO) - 1LL * to_rem * pow256 % MODO) * 256 + to_add) % MODO;
    return _hash;
}

int main () {

    fin >> A >> B;
    lenA = strlen (A);
    lenB = strlen (B);

    for (int i = 1; i < lenA; ++ i) {

        pow256 = (1LL * pow256 * 256) % MODO;
    }

    hashA = create_hash (A, lenA);
    hashB = create_hash (B, lenA);

    for (int i = 0; i < lenB - lenA; ++ i) {
        if (hashA == hashB) {
            ++ sol;
            if (sol <= 1000) {
                Pos.push_back (i);
            }
        }

        hashB = roll_hash (hashB, B[i], B[i + lenA]);
    }

    fout << sol << "\n";

    for (auto it : Pos) {
        fout << it << " ";
    }


    return 0;
}