Cod sursa(job #889635)

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

#define nMax 2000005

char Pattern[nMax], Text[nMax];

int lenText, lenPattern;
int Next[nMax];

int nSol;
int Sol[nMax];

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;
            k = Next[k];
        }
    }

}

void Write(){

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

    for(int i=1; i<=nSol; 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;

}