Cod sursa(job #1189955)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 24 mai 2014 00:24:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

const int maxl = 2000006;

char a[maxl],b[maxl];
int k,p[maxl];
int poz[1005];
int n,m,nr=0;

void kmp(char *a,int n,char *b,int m){
     int i;
     p[1]=0;
     k=0;
     
     for(i=2;i<=n;i++){
                       while(k>0 && a[k+1]!=a[i]) k=p[k];
                       if(a[k+1]==a[i]) k++;
                       p[i]=k;
                      }
     
     k=0;
     for(i=1;i<=m;i++){
                       while(k>0 && a[k+1]!=b[i]) k=p[k];
                       if(a[k+1]==b[i]) k++;
                       if(k==n){ nr++; if(nr<=1000) poz[nr]=i-n; }
                      }
}

void tipar(int nr){
     int i;
     fo<<nr<<"\n";
     for(i=1;i<=nr;i++) fo<<poz[i]<<" ";
}

int main(){
    fi>>(a+1); n=strlen(a+1);
    fi>>(b+1); m=strlen(b+1);
    
    kmp(a,n,b,m);
    
    tipar(nr);
    
    fi.close();
    fo.close();
    return 0;
}