Cod sursa(job #2352732)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 23 februarie 2019 17:15:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

#define MAXN 50005

int N, M;
char A[MAXN], B[MAXN];

int LPS[MAXN];
void ComputeLPS() {
    int Len = 0;
    for (int i=2; i<=M; ++i) {
        while (Len && B[Len+1] != B[i])
            Len = LPS[Len];
        if (B[Len+1] == B[i])
            ++ Len;
        LPS[i] = Len;
    }
}

std::vector <int> Ans;
void KMP() {
    ComputeLPS();
    int Len = 0;
    for (int i=1; i<=N; ++i) {
        while (Len && A[i] != B[Len+1])
            Len = LPS[Len];
        if (B[Len+1] == A[i])
            ++Len;

        if (Len == M) {
            if (Ans.size() <= 1000)
                Ans.push_back(i-M);
        }
    }
}

std::ifstream In ("strmatch.in");
std::ofstream Out("strmatch.out");

void Citire() {
    In >> B+1 >> A+1;
    N = strlen(A+1);
    M = strlen(B+1);
}

void Rezolvare() {
    KMP();
    Out << Ans.size() << '\n';
    for (auto idx:Ans)
        Out << idx << ' ';
}

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

    return 0;
}