Cod sursa(job #522937)

Utilizator tlapusanlapusan tudor tlapusan Data 16 ianuarie 2011 18:31:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<fstream.h>
#include<string.h>
using namespace std;

#define PI_NR 2000000

ifstream in("strmatch.in");
ofstream out("strmatch.out");
string n, m;
int pi[PI_NR];
int result[PI_NR];
int nrResult;

void read(){
     in>>n;
     in>>m;     
}

void makePI(){
     int k = 0;
     int nrN = n.length();
     pi[0] = 0;
     
     
     for(int i = 1; i < nrN; i++){
           while( k > 0 && n[k] != n[i]){
                  k = pi[k - 1];
           }
           if(n[k] == n[i]){
                  k = k + 1;        
           }       
           pi[i] = k;                        
     }
}

void showPI(){
     for(int i = 0; i < n.length(); i++){
             out<<pi[i] << " ";                   
     }
}

void solveKMP(){
     int nrN = n.length();
     int nrM = m.length();
     int k = 0;
     
     for(int i = 0; i < nrM; i++){
             while(k > 0 && n[k] != m[i]){
                     k = pi[k - 1];
             }           
             
             if(n[k] == m[i]){
                     k = k + 1;
             }
             if(k == nrN){
                  result[nrResult] = i - nrN + 1;
                  nrResult += 1;
                  
             }
     }
}

void showResult(){
     out<< nrResult<< "\n";
     for(int i = 0; i < nrResult; i++){
             out<< result[i]<< " ";
     }
}

int main(){
    read();
    makePI();
    //showPI();
    solveKMP();
    showResult();
    
    return 0;    
}