Cod sursa(job #390311)

Utilizator vladiiIonescu Vlad vladii Data 3 februarie 2010 14:46:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
using namespace std;

int Urm[2000002], sol[1002];
char T[2000002], P[2000002];

int main() {
    FILE *f1=fopen("strmatch.in", "r"), *f2=fopen("strmatch.out", "w");
    int i, j, p, q, t, k, nr=0;
    char c;
    fscanf(f1, "%s", &P);
    fscanf(f1, "%c", &c);
    fscanf(f1, "%s", &T);
    p=strlen(P); t=strlen(T);
    //construiesc functia prefix pentru T
    Urm[0]=0; k=-1;
    for(i=1; i<p; i++) {
         while(k>0 && P[i]!=P[k+1]) {
              k=Urm[k];
         }
         if(P[i]==P[k+1]) { 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; }
         }
    }
    fprintf(f2, "%d\n", nr);
    if(nr>1000) { nr=1000; }
    for(i=0; i<nr; i++) {
         fprintf(f2, "%d ", sol[i]);
    }
    fclose(f1); fclose(f2);
    return 0;
}