尝试和后缀树实现

Question

我已经学习了尝试和后缀树并希望实现相同。请分享一些链接，我可以从中了解实施的结构和基本思路。

任何好的例子，如果包括，将是一个加号。在C.

Answer 1

的Ç算法库（http://fragglet.github.io/c-algorithms/）

实现提供了一个Trie implementation in C。它是开源的，具有BSD风格的许可证。

C中的一个后缀树的实现可以在这里找到：https://github.com/0xtonyxia/suffix-tree

我希望帮助。

Answer 2

#include<stdio.h> 
#include<conio.h> 
#include<stdlib.h> 
#include<string.h> 

typedef struct trie trie; 
struct trie 
{ 
     char key; 
     trie *next,*children; 
}; 

trie *newnode(char s) 
{ 
    trie *t=(trie *)malloc(sizeof(trie)); 
    t->key=s; 
    t->next=t->children=NULL; 
} 

void insert(trie **t,char *s,int start) 
{if(s[start]=='\0') 
        { 
          *t=newnode('#'); 
          return; 
        } 
        if(*t==NULL) 
        { 
           *t=newnode(s[start]); 
           insert(&(*t)->children,s,start+1); 
        }  
        if((*t)->key==s[start]) 
        insert(&(*t)->children,s,start+1); 
        else 
        insert(&(*t)->next,s,start); 
} 


bool search(trie *t ,char *s,int start) 
{ 


    if(t==NULL) 
    return false; 

    if(t->key=='#' && s[start]=='\0') 
    return true; 

    if(t->key!='#' && s[start]=='\0' || t->key=='#' && s[start]!='\0') 
    return false; 

    if(t->key==s[start]) 
    return search(t->children,s,start+1); 

    else 
    return search(t->next,s,start); 

    return false; 
} 

/*void push(trie **t ,char *str) 
{      int i=0; 
         for(i=0;i<strlen(str);i++) 
         insert(t,str[i]); 
}*/ 

main() 
{  int i=0; 

     trie *t=NULL; 
     char ch='y'; 
     while(ch=='y') 
     {    
        {char str[20]; 
        fflush(stdin); 
        printf("Enter the word "); 
        gets(str); 


        insert(&t,str,0); 
        } 
        // push(&t,str); 
        fflush(stdin); 
        printf("more y/n ::"); 
        ch=getchar(); 
     } 

     ch='y'; 
     while(ch=='y') 
     {char str[20]; 
     fflush(stdin); 
     printf("Enter the string you want to search::"); 
     gets(str); 

     fflush(stdin); 
     if(search(t,str,0)) 
     printf("Found"); 
     else 
     printf("Not Found"); 

     printf("\n more y/n ::"); 
     scanf("%c",&ch); 

     } 

    getch(); 

} 

Answer 3

下面是我发现的非常有用的链接。

上后缀树（讲座3至第5讲） 谷歌SCICOMP讲座5

6小时讲座（最长公共子串：O（n）的后缀树，排序后缀）

广义后缀树实现 http://www.geeksforgeeks.org/generalized-suffix-tree-1/

快速串与后缀树 http://marknelson.us/1996/08/01/suffix-trees/

搜索查找维基百科Ukkonen算法。 注意：无法发布超过2个链接会导致声誉不够。

Answer 4

#include <iostream> 
#include <string.h> 
using namespace std; 
int high; 
struct stnode 
{ 
    stnode* ptr[27]; 
    int start; 
    int end; 
    stnode(int s,int e) 
    { 
     for (int i = 0; i < 27; ++i) 
     { 
      ptr[i]=NULL; 
     } 
     start=s; 
     end=e; 
    } 
}*root=NULL; 


stnode* fun(stnode* child,string str,int ind) 
{ 
    int s=child->start; 
    while(s<=child->end&&str.at(s)==str.at(ind)) 
     { 
      s++; 
      ind++; 
     } 
    if(s<=child->end) 
    { 
     child->ptr[str.at(ind)-'a']=new stnode(ind,high); 
     if(str.at(s)=='$') 
      child->ptr[26]=new stnode(s,child->end); 
     else 
      child->ptr[str.at(s)-'a']=new stnode(s,child->end); 
     child->end=s-1; 
     return child; 
    } 
    else 
    { 
     if(child->ptr[str.at(ind)-'a']) 
     { 
      child->ptr[str.at(ind)-'a']=fun(child->ptr[str.at(ind)-'a'],str,ind); 
      return child; 
     } 
     else 
     { 
      child->ptr[str.at(ind)-'a']=new stnode(ind,high); 
      return child; 
     } 
    } 

} 



stnode* create(stnode* root,string str,int ind) 
{ 
    if(!root) 
    { 
     root=new stnode(ind,high); 
     return root; 
    } 
    if(str.at(ind)=='$') 
    { 
     root->ptr[26]=new stnode(ind,high); 
     return root; 
    } 
    if(!root->ptr[str.at(ind)-'a']) 
    { 
     root->ptr[str.at(ind)-'a']=new stnode(ind,high); 
     return root; 
    } 
    root->ptr[str.at(ind)-'a']=fun(root->ptr[str.at(ind)-'a'],str,ind); 
    return root; 
} 



void display(stnode* root,string str) 
{ 
    if(!root) 
     return; 
    if(root->start!=-1) 
    { 
     for(int i=root->start;i<=root->end;i++) 
     { 
      cout<<str.at(i); 
     } 
     cout<<"\n"; 
    } 
    for(int i=0;i<27;i++) 
    { 
     display(root->ptr[i],str); 
    } 
} 


int main(int argc, char const *argv[]) 
{ 
    string str; 
    cout<<"enter the string.\n"; 
    cin>>str; 
    str=str+"$"; 
    high=str.length()-1; 

    root=new stnode(-1,-1); 

    for(int i=str.length()-1;i>=0;i--) 
    { 
     root=create(root,str,i); 
     display(root,str); 
     cout<<"\n\n\n"; 
    } 

    return 0; 
}