Cod sursa(job #1976889)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 4 mai 2017 15:10:04
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 2000002

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

char A[2 * NMAX];
int Z[2 * NMAX];

void Zalgo(const int N, const int start) {

    Z[0] = N;

    int st = 0, dr = 0;
    for (int i = 1; i < N; ++i) {

        if (i > dr) {
            st = dr = i;

            while (dr < N && A[dr] == A[dr - i])
                dr++;

            Z[i] = dr - i;
            dr--;
        }
        else {

            int k = i - st;

            if (Z[k] < dr - i + 1)
                Z[i] = Z[k];
            else {

                while (dr < N && A[dr] == A[dr - i])
                    dr++;

                Z[i] = dr - i;
                dr--;
            }
        }
    }

    vector<int> poz;
    int nrMatches = 0;

    for (int i = start; i < N; ++i) {
        if (Z[i] == start - 1) {

            nrMatches++;

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

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

int main() {

    fin >> A;

    int N = strlen(A);

    A[N] = '#';
    A[N + 1] = 0;

    int start = N + 1;

    fin >> (A + N + 1);

    N = strlen(A);

    Zalgo(N, start);

    return 0;
}