Cod sursa(job #1548285)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 10 decembrie 2015 18:52:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 2e6;
const int kPrint = 1000;

char P[kMaxN + 1], S[kMaxN + 1];
int pi[kMaxN];
int pos[kPrint];

int main(void) {
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    int m, n, k, q;

    in >> P >> S;
    in.close();

    m = strlen(P); n = strlen(S);
    for (int i = 1; i < m; i++) {
        while ((k > 0) && (P[k] != P[i])) {
            k = pi[k - 1];
        }
        if (P[k] == P[i]) {
            k++;
        }
        pi[i] = k;
    }
    k = 0;
    q = 0;
    for (int i = 0; i < n; i++) {
        while ((k > 0) && (P[k] != S[i])) {
            k = pi[k - 1];
        }
        if (P[k] == S[i]) {
            k++;
        }
        if (k == m) {
            if (q < kPrint) {
                pos[q] = i - m + 1;
            }
            q++;
        }
    }
    out << q << '\n';
    if (q > kPrint) {
        q = kPrint;
    }
    for (int i = 0; i < q; i++) {
        out << pos[i] << ' ';
    }
    out.close();
    return 0;
}