Cod sursa(job #2532893)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 28 ianuarie 2020 16:11:41
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <string>
#include <vector>

#define input "strmatch.in"
#define output "strmatch.out"
#define D 128
#define Q 131

using namespace std;

ifstream in(input);
ofstream out(output);

string A, B;
vector < int > sol;
int M, N;

int fasto_expo(int base, int exp)
{
    if(!exp) return 1;
    if(exp == 1) return base % Q;
    if(exp % 2) return base * fasto_expo((base * base) % Q, exp / 2) % Q;
    return fasto_expo((base * base) % Q, exp / 2) % Q;
}

void Read_Data()
{
    in >> A >> B;
    M = A.size();
    N = B.size();
}

bool Manual_Check(int k)
{
    for(int i = 0; i < M; i++)
        if(A[i] != B[i + k]) return false;
    return true;
}

void Rabin_Karp()
{
    int h = fasto_expo(D, M - 1) % Q, P = 0, T0 = 0;
    for(int i = 0; i < M; i++)
    {
        P = (D * P + A[i]) % Q;
        T0 = (D * T0 + B[i]) % Q;
    }
    for(int k = 0; k <= N - M; k++)
    {
        if(P == T0)
            if(Manual_Check(k)) sol.push_back(k);
        T0 = (T0 + D * Q - B[k] * h + 2 * Q) % Q;
        T0 = (T0 * D + B[k + M]) % Q;
    }
}

void Print_Sol()
{
    out << sol.size() << "\n";
    int a = sol.size();
    for(unsigned i = 0; i < min(a, 1000); i++)
        out << sol[i] << " ";
}

int main()
{
    Read_Data();
    Rabin_Karp();
    Print_Sol();
    return 0;
}