Cod sursa(job #186933)

Utilizator drag0shSandulescu Dragos drag0sh Data 29 aprilie 2008 08:51:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream.h>
#include <string.h>
#define NMAX 2000001

int Urm[NMAX];
char T[NMAX], P[NMAX];
int n, m, nrez, rez[1001];

void prefix(char *P){
    int k=-1, x;
    Urm[0]=-1;
    for(x=1; x<m; x++){
        while(k>=0 && P[k+1]!=P[x]) k=Urm[k];
        if(P[k+1]==P[x]) k++;
        Urm[x]=k;
    }
}

int main(){
    int i, x=-1;
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f.getline(P, NMAX);
    f.getline(T, NMAX);
    n=strlen(T); m=strlen(P);
    prefix(P);
    for(i=0; i<n; i++){
        while(x>=0 && P[x+1]!=T[i]) x=Urm[x];
        if(P[x+1]==T[i]) x++;
        if(x==m-1){
            if(nrez<1000)rez[nrez++]=i-m+1;
            else nrez++;
            x=Urm[x];
        }
    }
    g<<nrez<<"\n";
    if(nrez>1000) nrez=1000;
    for(i=0; i<nrez; i++)
        g<<rez[i]<<" ";
    return 0;
}