Cod sursa(job #1614975)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 26 februarie 2016 12:30:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <cstring>

using namespace std;

const int MAX_N = 2000000;
const int MAX_MATCH = 1000;

char A[2 * MAX_N + 2];

int Z[2 * MAX_N + 1];

int match[MAX_MATCH];

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin.tie(0);
    ios_base::sync_with_stdio(false);

    int N, M;
    int st, fn, matches;

    fin >> A;
    N = strlen(A);
    A[N] = '$';
    fin >> (A + N + 1);
    N += (M = strlen(A + N + 1)) + 1;

    st = 0, fn = 0;

    for (int i = 1; i < N; ++ i) {
        if (i <= fn) {
            Z[i] = min(Z[i - st], fn - i + 1);
        }
        while (A[Z[i]] == A[i + Z[i]]) {
            ++ Z[i];
        }
        if (i + Z[i] - 1 > fn) {
            st = i;
            fn = i + Z[i] - 1;
        }
    }

    matches = 0;
    for (int i = N - M; i < N; ++ i) {
        if (Z[i] == N - M - 1) {
            if (matches < MAX_MATCH) {
                match[matches] = i;
            }
            ++ matches;
        }
    }

    fout << matches << '\n'; matches = min(matches, MAX_MATCH);
    for (int i = 0; i < matches; ++ i) {
        fout << match[i] - N + M << " \n"[i == matches - 1];
    }
    fout.close();
    return 0;
}