Cod sursa(job #2298322)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 7 decembrie 2018 23:49:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>

#define MAXN 2000005
#define MAXANS 1000

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

void ComputeLPS() {
    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;
    }
}

int NAns;
std::vector <int> Ans;

void KMP() {
    ComputeLPS();
    for (int i=1, j=0; i<=M; ++i) {
        while (j && B[i] != A[j+1])
            j = LPS[j];
        if (B[i] == A[j+1])
            ++j;

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

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

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

void Rezolvare() {
    KMP();
    Out << NAns << '\n';
    for (int i=0; i<Ans.size(); ++i)
        Out << Ans[i] << ' ' ;
}

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

    return 0;
}