Cod sursa(job #143940)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 26 februarie 2008 22:54:42
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <string>
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX_N 2000000
#define MAX_S 1000
using namespace std;
char t[MAX_N+4],p[MAX_N+4];
int fpi[MAX_N+4],len,lng;
int nrsol,sol[MAX_S+1];

void iofile(void){
        freopen(FIN,"rt",stdin);
        freopen(FOUT,"wt",stdout);
        fgets(p+1,MAX_N+2,stdin);
        fgets(t+1,MAX_N+2,stdin);
        lng=strlen(t+1)-1;
        len=strlen(p+1)-1;
        fclose(stdin);
}


void calcul_pi(void){
        int i,q,k;
        k=0;
        fpi[1]=0;
        for (q=2;q<=len;q++){
                while (k && p[q]!=p[k+1]){
                        k=fpi[k];
                }
                if (p[q]==p[k+1]){k++;}
                fpi[q]=k;
        }
}

void kmp_match(void){
        int q,i;
        q=0;
        nrsol=0;
        for (i=1;i<=lng;i++){
                while (q && p[q+1]!=t[i]){
                        q=fpi[q];
                }
                if (p[q+1]==t[i]){q++;}
                if (q==len){
                        sol[++nrsol]=i-len;
                        q=fpi[q];
                        if (nrsol==1000){return ;}
                }
        }
}


void solve(void){
        int i;
        printf("%d\n",nrsol);
        for (i=1;i<nrsol;i++){
                printf("%d ",sol[i]);}
        printf("%d\n",sol[nrsol]);
        fclose(stdout);
}

int main(void){
        iofile();
        calcul_pi();
        kmp_match();
        solve();
        return 0;
}