Cod sursa(job #2333579)

Utilizator andysoloAndrei Solo andysolo Data 1 februarie 2019 14:35:21
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include<cstdio>
#include <vector>
#include <cstring>
/* #include "Euclid.cpp"
#include "EuclidExtended.cpp"
#include "LCS.cpp"
#include "RabinKarp.cpp" */
using namespace std;

class RabinKarp {

#define NMAX 2000000+3
#define P 73
#define MOD1 100007
#define MOD2 100021

private:
    char A[NMAX], B[NMAX];
    int AM1=0, AM2=0;
    int P1, P2;
    int N, M;
    vector<int> sol1;

    void precalc() {
        P1 = 1;
        P2 = 1;
        for (int i = 0; i < N; i++) {
            AM1 = (AM1 * P + A[i]) % MOD1;
            AM2 = (AM2 * P + A[i]) % MOD2;

            if (i) {
                P1 = (P1 * P) % MOD1;
                P2 = (P2 * P) % MOD2;
            }
        }
    }

public:

    void rabinKarp_main() {

        freopen("strmatch.in", "r", stdin);
        freopen("strmatch.out", "w", stdout);

        scanf("%s %s", A, B);

        int sol = 0;

        N = strlen(A);
        M = strlen(B);

        if(N>M)
        {
            printf("0");
            return;
        }

        precalc();

        long BM1 = 0, BM2 = 0;

        for (int i = 0; i < N; i++) {
            BM1 = (BM1 * P + B[i]) %MOD1;
            BM2 = (BM2 * P + B[i]) %MOD2;
        }

        if (BM1 == AM1 && BM2 == AM2)
            sol++,sol1.push_back(0);

        for (int i = N; i < M; i++) {
            BM1 = ((BM1 - ((B[i - N] * P1) % MOD1) + MOD1)  * P + B[i]) % MOD1;
            BM2 = ((BM2 - ((B[i - N] * P2) % MOD2) + MOD2)  * P + B[i]) % MOD2;

            if (BM1 == AM1 && BM2 == AM2)
                sol++, sol1.push_back(i-N+1);
        }

        printf("%d\n", sol);
        for (int i=0;i<=sol1.size() && i<1000;i++) {
            printf("%d ", sol1[i]);
        }

    }
} rabinKarp;

int main()
{
    rabinKarp.rabinKarp_main();
    return 0;
}