Cod sursa(job #1145530)

Utilizator swim406Teudan Adina swim406 Data 18 martie 2014 11:37:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdio.h>
#include <string.h>
#include <queue>
#define NMAX 2000005

using namespace std;

char A[NMAX], B[NMAX];
int L[NMAX];
queue <int> q;

void prefix() {
    int k, p;
    int m = strlen(A);
    L[1] = 0;
    for (p = 2; p <= m; ++p) {
        k = L[p-1];
        while (k > 0 && A[k+1] != A[p])
            k = L[k];
        if (A[k+1] == A[p])
            ++k;
        L[p] = k;
    }
    //for (int i = 1; i < m; ++i)
    //    printf ("%d ", L[i]);
}

void kmp() {
    int k, t, m, n, count = 0;
    m = strlen(A) - 1;
    n = strlen(B) - 1;
    k = 0;
    for (t = 1; t <= n; ++t) {
        while (k > 0 && A[k+1] != B[t])
            k = L[k];
        if (A[k+1] == B[t])
            ++k;
        if (k == m) {
            ++count;
            if (count <= 1000)
                q.push(t-m);
            k = L[k];
        }
    }
    printf ("%d\n", count);
    while (!q.empty()) {
        printf ("%d ", q.front());
        q.pop();
    }
    printf ("\n");
}

int main() {
    freopen ("strmatch.in", "r", stdin);
    freopen ("strmatch.out", "w", stdout);
    int m, i;
    scanf ("%s %s", A, B);
    m = strlen(A);
    for (i = m; i >= 1; --i)
        A[i] = A[i-1];
    m = strlen(B);
    for (i = m; i >= 1; --i)
        B[i] = B[i-1];
    prefix();
    kmp();
    return 0;
}