Cod sursa(job #261762)

Utilizator yonutzTalos Ionut yonutz Data 18 februarie 2009 19:18:27
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>  
#include <string.h>  

  
using namespace std;  
   
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;  
}