Cod sursa(job #390310)

Utilizator vladiiIonescu Vlad vladii Data 3 februarie 2010 14:42:06
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
using namespace std;

int Urm[2000001], sol[1001];
char T[2000001], P[2000001];

int main() {
    fstream f1, f2;
    int i, j, p, q, t, k, nr=0;
    f1.open("strmatch.in", ios::in);
    f1>>P>>T;
    f1.close();
    p=strlen(P); t=strlen(T);
    //construiesc functia prefix pentru T
    Urm[0]=0; k=0;
    for(i=1; i<p; i++) {
         while(k>0 && P[i]!=P[k]) {
              k=Urm[k];
         }
         if(P[i]==P[k]) { k++; }
         
         Urm[i]=k;
    }
    k=-1;
    for(i=0; i<t; i++) {
         while(k>0 && T[i]!=P[k+1]) {
              k=Urm[k];
         }
         if(T[i]==P[k+1]) { k++; }
         
         if(k==p-1) {
              nr++;
              if(nr<=1000) { sol[nr-1]=i-p+1; }
         }
    }
    f2.open("strmatch.out", ios::out);
    f2<<nr<<endl;
    if(nr>1000) { nr=1000; }
    for(i=0; i<nr; i++) {
         f2<<sol[i]<<" ";
    }
    f2<<endl;
    f2.close();
    return 0;
}