Cod sursa(job #889674)

Utilizator RengelBotocan Bogdan Rengel Data 24 februarie 2013 17:29:49
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <cstring>

#define nMax 2000005

char Pattern[nMax], Text[nMax];

int lenText, lenPattern;
int Next[nMax];

int nSol;
int Sol[nMax];

int min(int x, int y){

    if(x<y) return x;
    return y;

}

void Read(){

    scanf("%s %s", Pattern, Text);

}

void buildNext(){

    int k=0;
    for(int i=1; i<lenPattern; i++){
        if(Pattern[k] == Pattern[i])
            Next[i+1] = ++k;
        else
            Next[i+1] = k = 0;
    }

}

void Solve(){

    int k=0;
    for(int i=0; i<lenText; i++){
        if(Text[i] == Pattern[k])
            k++;
        else{
            if(k==lenPattern)
                Sol[++nSol] = i - k;
            if(k)
                i--;
            k = Next[k];
        }
    }

}

void Write(){

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

    for(int i=1; i<=min(nSol,1000); i++)
        printf("%d ", Sol[i]);

}

int main(){

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

    Read();

    lenText = strlen(Text);
    lenPattern = strlen(Pattern);

    buildNext();

    Solve();

    Write();

    return 0;

}