Cod sursa(job #194309)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 9 iunie 2008 18:42:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
using namespace std;
const int TMAX=2000002,PMAX=1001;
char T[TMAX],P[TMAX];
int n,m,pi[TMAX],poz[PMAX],nr;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void prefix(){
     int i,x=0;
     pi[0]=0;
     for (i=1;i<m;++i){
         while (x>0 && P[x]!=P[i]) x=pi[x-1];
         if (P[x]==P[i]) x++;
         pi[i]=x;
         }
     }
void kmp(){
     int i,x=0;
     for (i=0;i<n;++i){
         while (x>0 && P[x]!=T[i]) x=pi[x-1];
         if (P[x]==T[i]) x++;
         if (x==m) {  ++nr; 
                      if (nr<=1000) poz[nr]=i-m+1;
                      x=pi[x-1];}
         }
     g<<nr<<'\n';
     if (nr>1000) nr=1000;
     for (i=1;i<=nr;++i) g<<poz[i]<<' ';
     }
int main(){
    f.getline(P,TMAX);
    m=strlen(P);
    f.getline(T,TMAX);
    n=strlen(T);
    prefix();
    kmp();
    return 0;
    }