Cod sursa(job #2315412)

Utilizator andra_moldovanAndra Moldovan andra_moldovan Data 9 ianuarie 2019 22:22:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <cstring>
#include <vector>

#define MAXN 2000005

using namespace std;

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

char x[MAXN], y[MAXN];
vector <int> s;

int pi[MAXN];

inline void Read(int &N, int &M, char x[], char y[]) {
    fin >> (x + 1);
    N = strlen(x + 1);

    fin >> (y + 1);
    M = strlen(y + 1);
}

inline void Det_pi(int N, char x[], int pi[]) {
    int k = 0; pi[1] = 0;

    for (int i = 2; i <= N; i++) {
        while (k > 0 && x[i] != x[k + 1])
            k = pi[k];
        if (x[i] == x[k + 1])
            k++;
        pi[i] = k;
    }
}

inline void KMP(int N, int M, char x[], char y[], int &sol, int pi[]) {
    int k = 0; sol = 0;
    for (int i = 1; i <= M; i++) {
        while (k > 0 && y[i] != x[k + 1])
            k = pi[k];

        if (y[i] == x[k + 1])
            k++;

        if (k == N) {
            sol++;

            if (sol <= 1000)
                s.push_back(i - N);
            k = pi[k];
        }
    }
}

inline void Write(int sol) {
    fout << sol << "\n";

    for (auto i : s)
        fout << i << " ";
}

int main () {
    int N, M, sol;

    Read(N, M, x, y);
    Det_pi(N, x, pi);
    KMP(N, M, x, y, sol, pi);
    Write(sol);

    fin.close(); fout.close(); return 0;
}