Cod sursa(job #157603)

Utilizator FlorinC1996Florin C FlorinC1996 Data 13 martie 2008 09:56:13
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
 #include <cstring>   
#include <cstdio>   
const int nmax=2000001;   
char a[nmax],b[nmax];   
int pi[nmax],poz[1001],n,m;   
void prefix(){   
     int i,k;   
     pi[0]=-1;pi[1]=0;   
     for (i=2,k=0;i<=n;i++) {   
         while (k>0 && a[i-1]!=a[k]) k=pi[k];   
         if (a[i-1]==a[k]) k++;   
         pi[i]=k;}   
}   
void search(){   
     int i,k;   
     for (i=0,k=0;i+k<m;){   
         if (a[k]==b[i+k]){k++;   
                           if (k==n) {poz[0]++;   
                                      if (poz[0]<=1000) poz[poz[0]]=i;   
                                      i=i+n-pi[n];   
                                      k=pi[n];}   
                           }   
                     else {i=i+k-pi[k];   
                           if (k>0) k=pi[k];}   
                           }   
}   
int main(){   
    int i;   
    freopen("strmatch.in","r",stdin);   
    freopen("strmatch.out","w",stdout);   
    scanf("%s\n%s",a,b);   
    n=strlen(a);   
    m=strlen(b);   
    prefix();   
    search();   
    printf("%d\n",poz[0]);   
    if (poz[0]>1000) poz[0]=1000;   
    for (i=1;i<=poz[0];i++) printf("%d ",poz[i]);   
    fclose(stdout);   
}   
            
       
#include <cstring>
#include <cstdio>
const int nmax=2000001;
char a[nmax],b[nmax];
int pi[nmax],poz[1001],n,m;
void prefix(){
     int i,k;
     pi[0]=-1;pi[1]=0;
     for (i=2,k=0;i<=n;i++) {
         while (k>0 && a[i-1]!=a[k]) k=pi[k];
         if (a[i-1]==a[k]) k++;
         pi[i]=k;}
}
void search(){
     int i,k;
     for (i=0,k=0;i+k<m;){
         if (a[k]==b[i+k]){k++;
                           if (k==n) {poz[0]++;
                                      if (poz[0]<=1000) poz[poz[0]]=i;
                                      i=i+n-pi[n];
                                      k=pi[n];}
                           }
                     else {i=i+k-pi[k];
                           if (k>0) k=pi[k];}
                           }
}
int main(){
    int i;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s",a,b);
    n=strlen(a);
    m=strlen(b);
    prefix();
    search();
    printf("%d\n",poz[0]);
    if (poz[0]>1000) poz[0]=1000;
    for (i=1;i<=poz[0];i++) printf("%d ",poz[i]);
    fclose(stdout);
}