Cod sursa(job #794227)

Utilizator AndreyPAndrei Poenaru AndreyP Data 5 octombrie 2012 23:22:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#define L 2000001
#define N 1001

char A[L], B[L];
int pi[L];
int nRez, r[N];

inline void read() {
    std::ifstream fin("strmatch.in");
    fin >> (A + 1) >> (B + 1);
    fin.close();
}

void solve() {
    int q = 0, lenA = 1;
    pi[1] = 0;
    for (int i = 2; A[i] != '\0'; ++i, ++lenA) {
        while (q && A[q + 1] != A[i])
            q = pi[q];

        if (A[q + 1] == A[i])
            ++q;
        pi[i] = q;
    }

    q = 0;
    for (int i = 1; B[i] != '\0'; ++i) {
        while (q && A[q + 1] != B[i])
            q = pi[q];

        if (A[q + 1] == B[i])
            ++q;
        if (q == lenA) {
            ++nRez;
            if (r[0] < 1000)
                r[++r[0]] = i - lenA;
        }
    }
}

inline void print() {
    std::ofstream fout("strmatch.out");
    fout << nRez << '\n';
    if (nRez != 0) {
        fout << r[1];
        for (int i = 2; i <= r[0]; ++i)
            fout << ' ' << r[i];
        fout << '\n';
    }

    fout.close();
}

int main() {
    read();
    solve();
    print();

    return 0;
}