Cod sursa(job #1562726)

Utilizator Burbon13Burbon13 Burbon13 Data 5 ianuarie 2016 13:50:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <cstring>
using namespace std;

const int nmx = 2000002;

char A[nmx],B[nmx];
int la,lb;
int pr[nmx],af[1002];

void prefix() {
    int i = 1,j = 0;
    while(i < la) {
        if(A[i] == A[j]) {
            pr[i] = j + 1;
            ++ i;
            ++ j;
        } else if(j)
            j = pr[j-1];
        else
            ++  i;
    }
}

void kmp() {
    int i = 0,j = 0;
    while(j < lb) {
        if(A[i] == B[j]) {
            ++ i;
            ++ j;
            if(i == la) {
                ++ af[0];
                if(af[0] <= 1000)
                    af[af[0]] = j - i;
            }
        } else {
            if(i)
                i = pr[i-1];
            else
                ++ j;
        }
    }
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s", A);
    scanf("%s", B);

    la = strlen(A);
    lb = strlen(B);

    prefix();

    kmp();

    printf("%d\n", af[0]);
    int dist = (af[0] > 1000 ? 1000 : af[0]);
    for(int i = 1; i <= dist; ++i)
        printf("%d ", af[i]);

    return 0;
}