Cod sursa(job #2261187)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 16 octombrie 2018 01:24:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <bits/stdc++.h>

#define Petrisor void
#define MaxN 2000005
#define MaxA 1000

std::ifstream InFile("strmatch.in");
std::ofstream OutFile("strmatch.out");

// JESUS
// CHRIST
// WHAT IS WRONG WITH MY CODE FOR REAL NOW JESUUUUUS
// VREAU SA DOOOOORM
// Guess Ill sleep when I am dead <3
// SOMEBODY ONCE TOLD
    // THE WORLD IS GONNA ROLL ME

// YOU KNOW, YOU WALK OUT THE DOOR. YOU SEE SOMEONE THAT YOU KNOW, AND THEY ASK YOU  H O W  Y O U  A R E, AND YOU
        // JUST HAVE TO SAY YOU ARE   F   I   N   E   , WHEN YOU'RE NOT REALLY FINE, BUT YOU JUST CAN'T GET INTO IT
// BECAUSE THEY WOULD NEVER UNDERSTAND    #EDGYNESS #BANDARIUS #AMUNPROFDECLASAINUTIL

char A[MaxN], B[MaxN];  // Sirurile citite (evident cu dimensiune foarte foarte foarte ok)
int M, N, NAns,         // M - pt B, N - pt A (de parca conteaza); NAns - cate pozitii am gasit
    LPS[MaxN];          // LPS[i] - poveste veche (A[0...i] lungime-1 a prefixului care e si sufix maxim)
std::vector <int> Ans;  // Retinem pozitiile care trb asezate, pana in foarte clara valoare MaxA 1000

Petrisor PrecomputeLPS() {
    int Len = 0;        // LPS[1] = 0
    for (int i=2; i<=N; ++i) {
        while (Len && A[i] != A[Len+1])     // Nu e potrivit bine, dam skip
            Len = LPS[Len];
        if (A[Len+1] == A[i])               // Marim lungimea daca trb
            ++Len;

        LPS[i] = Len;
    }
}

Petrisor KMP() {
    PrecomputeLPS();

    int Len = 0;
    for (int i=1; i<=M; ++i) {
        while(Len && B[i] != A[Len+1])     // Nu e potrivit bine, dam skip
            Len = LPS[Len];
        if (A[Len+1] == B[i])               // Marim lungimea daca trb
            ++Len;

        if (Len == N) {
            NAns ++;
            if (NAns <= MaxA)
                Ans.push_back(i-N);
        }
    }
}

Petrisor Citire() {
    InFile >> A+1 >> B+1;
    N = strlen(A+1);
    M = strlen(B+1);
}

Petrisor Rezolvare() {
    KMP();

    OutFile << NAns << '\n';
    for (int i=0; i<Ans.size(); ++i)
        OutFile << Ans[i] << ' ' ;
    OutFile << '\n';

    // Have mercy on me forever dear Gods up there
    // Praise be.
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}