Cod sursa(job #2632457)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 3 iulie 2020 13:04:49
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

string a, b;

int MOD[2] = {100003, 666013};
int Put[2] = {127, 131};
int Power[2] = {1, 1};
int Val_A[2] = {0, 0};
int Val_B[2] = {0, 0};

void Solve () {
    if (a.size() > b.size()) {
        g << 0 << '\n';
        return;
    }

    for (int i = 0; i < a.size(); ++ i ) {
        for (int j = 0; j < 2; ++ j ) {
            Val_B[ j ] = (1LL * Val_B[ j ] * Put[ j ] % MOD[ j ] + b[ i ] - '0') % MOD[ j ];
            Val_A[ j ] = (1LL * Val_A[ j ] * Put[ j ] % MOD[ j ] + a[ i ] - '0') % MOD[ j ];
        }
    }
    for (int i = 1; i < a.size(); ++ i ) {
        for (int j = 0; j < 2; ++ j ) {
            Power[ j ] = (1LL * Power[ j ] * Put[ j ]) % MOD[ j ];
        }
    }

    vector <int> ans;

    if (Val_A[ 0 ] == Val_B[ 0 ] && Val_A[ 1 ] == Val_B[ 1 ])
        ans.push_back(0);

    for (int i = a.size(); i < b.size(); ++ i ) {
        for (int j = 0; j < 2; ++ j ) {
            Val_B[ j ] = ((Val_B[ j ] - ((b[ i - a.size() ] - '0') * Power[ j ]) % MOD[ j ] + MOD[ j ]) * Put[ j ] + (b[ i ] - '0')) % MOD[ j ];
        }

        if (Val_A[ 0 ] == Val_B[ 0 ] && Val_A[ 1 ] == Val_B[ 1 ]) {
            ans.push_back(i - a.size() + 1);
        }
    }

    g << ans.size() << '\n';
    for (int i = 0; i < min(1000, (int)ans.size()); ++ i ) {
        g << ans[ i ] << " ";
    }
}

int main()
{
    f >> a >> b;

    Solve();

    return 0;
}