Cod sursa(job #793026)

Utilizator Sm3USmeu Rares Sm3U Data 1 octombrie 2012 19:56:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <cstring>
#define lungimeMax 2000010

using namespace std;

char A[lungimeMax];
char B[lungimeMax];
int prefix[lungimeMax];
int lungimeA;
int lungimeB;
int afisare[1000];
int lungimeAfisare;

void Prefix(){
    int pos = 0;
    for (int i = 2; i <= lungimeA; ++ i){
        while (pos && A[i] != A[pos + 1]){
            pos = prefix[pos];
        }
        if (A[i] == A[pos + 1]){
            pos ++;
        }
        prefix[i] = pos;
    }
}

void Citire(){
    gets(A + 1);
    gets(B + 1);
    lungimeA = strlen (A + 1);
    lungimeB = strlen (B + 1);
}

void Kmp(){
    int pos = 0;
    for (int i = 1; i <= lungimeB; ++ i){
        while (pos && B[i] != A[pos + 1]){
            pos = prefix[pos];
        }
        if (B[i] == A[pos + 1]){
            pos ++;
        }
        if (pos == lungimeA){
            if (lungimeAfisare < 1000){
                afisare[lungimeAfisare ++] = i - pos;
            }
        }
    }
}

void Afisare(){
    printf ("%d\n", lungimeAfisare);
    for (int i = 0; i < lungimeAfisare; ++ i){
        printf ("%d ", afisare[i]);
    }
}

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

    Citire();
    Prefix();
    Kmp();
    Afisare();

    return 0;
}