Cod sursa(job #1976879)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 4 mai 2017 14:29:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 2000002

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int pi[NMAX];
char A[NMAX], B[NMAX];

void prefix(const int N) {

    int k = 0;

    for (int i = 2; i <= N; ++i) {

        while (k > 0 && A[k + 1] != A[i])
            k = pi[k];

        if (A[k + 1] == A[i])
            k++;

        pi[i] = k;
    }
}

void match(const int N, const int M) {

    vector<int> poz;
    int k = 0, nrMatches = 0;

    for (int i = 1; i <= M; ++i) {

        while (k > 0 && A[k + 1] != B[i])
            k = pi[k];

        if (A[k + 1] == B[i])
            k++;

        if (k == N) {

            nrMatches++;

            if (nrMatches <= 1000)
                poz.push_back(i - N);
        }
    }

    fout << nrMatches << "\n";

    for (auto val: poz)
        fout << val << " ";
}

int main() {

    fin >> (A + 1) >> (B + 1);

    int N = strlen(A + 1);
    int M = strlen(B + 1);

    if (N > M) {
        fout << 0;
        return 0;
    }

    prefix(N);

    match(N, M);

    return 0;
}