Cod sursa(job #143969)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 26 februarie 2008 23:26:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 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,MAX_N+2,stdin);
        fgets(t,MAX_N+2,stdin);
        for (; (t[lng]>='A' && t[lng]<='Z') || (t[lng]>='a' && t[lng]<='z')
        ||(t[lng]>='0' && t[lng]<='9');lng++);
        for (; (p[len]>='A' && p[len]<='Z')||(p[len]>='a' && p[len]<='z')
        ||(p[len]>='0' && p[len]<='9');len++);
        for (int i=lng;i;--i){t[i]=t[i-1];}
        for (int i=len;i;--i){p[i]=p[i-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){
                        ++nrsol;
                        if (nrsol<=1000){
                                sol[nrsol]=i-len;
                                }
                        q=fpi[q];

                }
        }
}


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

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