Cod sursa(job #1150825)

Utilizator cbanu96Banu Cristian cbanu96 Data 23 martie 2014 16:20:16
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define FILEIN "strmatch.in"
#define FILEOUT "strmatch.out"
#define LENMAX 2000005

int SolCount;
vector<int> sol;

char A[LENMAX], B[LENMAX], AL, BL;
int P[LENMAX];

void prefix() {
    P[1] = 0;

    for ( int i = 2, k = 0; i <= AL; i++ ) {
        while ( k > 0 && A[k+1] != A[i]) {
            k = P[k];
        }

        if (A[k+1] == A[i])
            k++;

        P[i] = k;
    }
}

void kmp() {
    prefix();

    for ( int i = 1, k = 0; i <= BL; i++ ) {
        while ( k > 0 && A[k+1] != B[i]) {
            k = P[k];
        }

        if (A[k+1] == B[i])
            k++;

        if (k == AL) {
            SolCount++;
            if (SolCount <= 1000)
                sol.push_back(i - AL);
        }
    }
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    fgets(A+1, LENMAX, stdin);
    fgets(B+1, LENMAX, stdin);

    if (A[strlen(A+1)] == '\n')
        A[strlen(A+1)] = '\0';

    if (B[strlen(B+1)] == '\n')
        B[strlen(B+1)] = '\0';

    AL = strlen(A+1); BL = strlen(B+1);

    kmp();

    printf("%d\n", SolCount);

    for ( int i = 0; i < sol.size(); i++ ) {
        printf("%d ", sol[i]);
    }

    printf("\n");

    return 0;
}