Cod sursa(job #2261184)

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

#define MaxN 2000005
#define MaxA 1000

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

char A[MaxN], B[MaxN];
int M, N, NAns, Ans[MaxA+5],
    LPS[MaxN];

void PrecomputeLPS() {
    int Len = 0;
    for (int i=2; i<=N; ++i) {
        while (Len && A[i] != A[Len+1])
            Len = LPS[Len];
        if (A[Len+1] == A[i])
            ++Len;

        LPS[i] = Len;
    }
}

void KMP() {
    PrecomputeLPS();

    int Len = 0;
    for (int i=1; i<=M; ++i) {
        while(Len && B[i] != A[Len+1])
            Len = LPS[Len];
        if (A[Len+1] == B[i])
            ++Len;

        if (Len == N) {
            if (NAns+1 <= MaxA)
                Ans[++NAns] = i-N;
        }
    }
}

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

void Rezolvare() {
    KMP();

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

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

    return 0;
}