Cod sursa(job #390446)

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

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

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