Cod sursa(job #2736006)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 3 aprilie 2021 02:39:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int p1 = 666013;
const int p2 = 666019;
vector <int> sol;
string A, B;

int main()
{
    in >> A >> B;
    int n = A.size();
    int m = B.size();
    int hshA1 = 0;
    int hshA2 = 0;
    int put1 = 1;
    int put2 = 1;
    for(int i = 0; i < n; i++)
    {
        hshA1 = (26LL * hshA1 + A[i]) % p1;
        hshA2 = (26LL * hshA2 + A[i]) % p2;
    }
    //cerr << hshA1 << " " << hshA2 << "\n";
    long long act1 = 0;
    long long act2 = 0;
    for(int i = 0; i < min(n - 1, m); i++)
    {
        act1 = (26LL * act1 + B[i]) % p1;
        act2 = (26LL * act2 + B[i]) % p2;
        put1 = (put1 * 26) % p1;
        put2 = (put2 * 26) % p2;
    }
    for(int i = n - 1; i < m; i++)
    {
        act1 = (26LL * act1 + B[i]) % p1;
        act2 = (26LL * act2 + B[i]) % p2;
        //cerr << act1 << " " << act2 << "\n";
        if(act1 == hshA1 && act2 == hshA2)
            sol.push_back(i - n + 1);
        act1 = (act1 - put1 * B[i - n + 1] % p1 + p1) % p1;
        act2 = (act2 - put2 * B[i - n + 1] % p2 + p2) % p2;
    }
    out << sol.size() << "\n";
    for(int i = 0; i < min(1000, (int)sol.size()); i++)
        out << sol[i] << " ";
    out << "\n";
    return 0;
}