Wie kann ich einen Präfixbaum erstellen?

Question

Ich brauche einen Präfix-Baum zu tun, dass der Benutzer ein Wort eingeben und das Programm der Präfixbaums angezeigt Der Ausgang sein soll: String: Banana

ein

na

ana

nana

anana

Banana

Answer 1

Dies ist in C++

#include <iostream> 
#include <string.h> 
#include <fstream> 

using namespace std; 
int primero; 
struct nodo //Se crea el nodo 
{ 
nodo* ptr[27]; //Las 26 ramas 
int prinodo; 
int ultimon; 
nodo(int s,int e) 
{ 
    for (int i = 0; i < 27; ++i) 
    { 
     ptr[i]=NULL; 
    } 
    prinodo=s; 
    ultimon=e; 
} 
}*raiz=NULL; 


nodo* fun(nodo* hijo,string str,int ind) 
{ 
int s=hijo->prinodo; //Se van creando las ramas 
while(s<=hijo->ultimon&&str.at(s)==str.at(ind)) 
    { 
     s++; 
     ind++; 
    } 
if(s<=hijo->ultimon) // 
{ 
    hijo->ptr[str.at(ind)-'a']=new nodo(ind,primero); 
    if(str.at(s)=='$') 
     hijo->ptr[26]=new nodo(s,hijo->ultimon); 
    else 
     hijo->ptr[str.at(s)-'a']=new nodo(s,hijo->ultimon); 
    hijo->ultimon=s-1; 
    return hijo; 
} 
else 
{ 
    if(hijo->ptr[str.at(ind)-'a']) 
    { 
     hijo->ptr[str.at(ind)-'a']=fun(hijo->ptr[str.at(ind)-'a'],str,ind); 
     return hijo; 
    } 
    else 
    { 
     hijo->ptr[str.at(ind)-'a']=new nodo(ind,primero); 
     return hijo; 
    } 
    } 

    } 




nodo* crea(nodo* raiz,string str,int ind) 
{ 
if(!raiz) 
{ 
    raiz=new nodo(ind,primero); 
    return raiz; 
} 
if(str.at(ind)=='$') 
{ 
    raiz->ptr[26]=new nodo(ind,primero); 
    return raiz; 
} 
if(!raiz->ptr[str.at(ind)-'a']) 
{ 
    raiz->ptr[str.at(ind)-'a']=new nodo(ind,primero); 
    return raiz; 
} 
raiz->ptr[str.at(ind)-'a']=fun(raiz->ptr[str.at(ind)-'a'],str,ind); 
return raiz; 
} 



void Imprime(nodo* raiz,string str) 
    { 
if(!raiz) 
    return; 
if(raiz->prinodo!=-1) 
{ 
    for(int i=raiz->prinodo;i<=raiz->ultimon;i++) 
    { 
     cout<<str.at(i); 
    } 
    cout<<"\n";Imprime 
} 
for(int i=0;i<27;i++) 
{ 
    Imprime(raiz->ptr[i],str); 
} 
} 


int main(int argc, char const *argv[]) 
{ 
    std::cout << "Nombre del archivo: \n" ; // Pregunta el nombre del archivo a buscar la cadena 
    std::string input ; 
    std::getline(std::cin , input) ; 
    std::ifstream infile(input.c_str() , std::ios::in) ; 
    std::string file(input) ; 
    std::cout << "Inserte el número de linea de la cadena: " ; //Pregunta el nombre de la línea donde se buscará la cadena 
    std::getline(std::cin , input) ; 
    int linenumber = std::stoi(input) ; 
    int lines_read = 0 ; 
    std::string line ; 
    if (infile.is_open()) { 
     while (infile) { 
    getline(infile , line) ; 
    lines_read++ ; 
    if (lines_read == linenumber) { 
     std::cout <<"Palabra: "<< line << std::endl ; //Imprime la palabra 

        primero=line.length()-1; 
       line=line+"$"; 
        raiz=new nodo(-1,-1); 

         for(int i=line.length()-1;i>=0;i--) //Hace la separación dela palabra e iprime los prefijosImprime 
         { 
          raiz=crea(raiz,line,i); 
          Imprime(raiz,line); 
          cout<<""; 
         } 

      break; 
     } 
     } 

    } 


return 0; 
}