广义后缀树1-yiteyi-C++库

在之前的后缀树文章中，我们为一个字符串创建了后缀树，然后查询该树以查找字符串子串检查 , 搜索所有模式 , 最长重复子串和内置后缀数组（所有线性时间操作）。在涉及多个字符串的情况下，还有很多其他问题。 e、 g.在文本文件或字典、拼写检查器、电话簿中进行模式搜索，自动完成 , 最长公共子串问题 , 最长回文子串和更多 . 对于此类操作，所有涉及的字符串都需要索引，以便更快地搜索和检索。一种方法是使用后缀trie或后缀树。我们将在这里讨论后缀树。由一组字符串组成的后缀树称为广义后缀树 . 我们将讨论一种简单的构建方法广义后缀树来这里 只有两条线 . 稍后，我们将讨论另一种构建方法广义后缀树对于 两个或更多字符串 . 这里我们将使用后缀树实现对于已经讨论过的一个字符串，请稍加修改以构建它广义后缀树 . 让我们考虑两个字符串x和y，我们要为它们建立广义后缀树。为此，我们将创建一个新字符串X#Y$，其中#和$都是终端符号（必须是唯一的）。然后我们将为X#Y$建立后缀树，这将是X和Y的通用后缀树。相同的逻辑将应用于两个以上的字符串（即，使用唯一的终端符号连接所有字符串，然后为连接的字符串建立后缀树）。假设X=xabxa，Y=babxba X#Y$=xabxa#babxba$ 如果我们运行在 Ukkonen后缀树构造——第6部分对于字符串xabxa#babxba$，我们得到以下输出： 输出：

null

图片[1]-广义后缀树1-yiteyi-C++库

图片视图：

图片[2]-广义后缀树1-yiteyi-C++库

我们可以使用这棵树来解决一些问题，但我们可以通过删除路径标签上不需要的子字符串来对其进行一些改进。一个路径标签应该只包含来自一个输入字符串的子字符串，因此如果有路径标签包含来自多个输入字符串的子字符串，我们可以只保留对应于一个字符串的初始部分，并删除所有后续部分。例如，对于路径标签#babxba$、a#babxba$和bxa#babxba$，我们可以删除babxba$（属于2） ^钕输入字符串），然后新的路径标签将分别为#、a#和bxa#。通过此更改，上图将如下所示：

Generalized Suffix Tree

下面的实现是建立在最初的实施 .这里我们将删除路径标签上不需要的字符。如果路径标签中有“#”字符，那么我们将修剪该路径标签中“#”之后的所有字符。

注意：这个实现只为两个字符串X和Y构建通用后缀树，这两个字符串被连接为X#Y$

C

                         // A C program to implement Ukkonen's Suffix Tree Construction                       
                         // And then build generalized suffix tree                       
                         #include <stdio.h>                       
                         #include <string.h>                       
                         #include <stdlib.h>                       
                         #define MAX_CHAR 256                       
                                   
                         struct                                     SuffixTreeNode {                       
                                                 struct                                     SuffixTreeNode *children[MAX_CHAR];                       
                                   
                                                 //pointer to other node via suffix link                       
                                                 struct                                     SuffixTreeNode *suffixLink;                       
                                   
                                                 /*(start, end) interval specifies the edge, by which the                       
                                                 node is connected to its parent node. Each edge will                       
                                                 connect two nodes,  one parent and one child, and                       
                                                 (start, end) interval of a given edge  will be stored                       
                                                 in the child node. Lets say there are two nods A and B                       
                                                 connected by an edge with indices (5, 8) then this                       
                                                 indices (5, 8) will be stored in node B. */                       
                                                 int                                     start;                       
                                                 int                                     *end;                       
                                   
                                                 /*for leaf nodes, it stores the index of suffix for                       
                                                 the path  from root to leaf*/                       
                                                 int                                     suffixIndex;                       
                         };                       
                                   
                         typedef                                     struct                                     SuffixTreeNode Node;                       
                                   
                         char                                     text[100];                                     //Input string                       
                         Node *root = NULL;                                     //Pointer to root node                       
                                   
                         /*lastNewNode will point to newly created internal node,                       
                                                 waiting for it's suffix link to be set, which might get                       
                                                 a new suffix link (other than root) in next extension of                       
                                                 same phase. lastNewNode will be set to NULL when last                       
                                                 newly created internal node (if there is any) got it's                       
                                                 suffix link reset to new internal node created in next                       
                                                 extension of same phase. */                       
                         Node *lastNewNode = NULL;                       
                         Node *activeNode = NULL;                       
                                   
                         /*activeEdge is represented as input string character                       
                                                 index (not the character itself)*/                       
                         int                                     activeEdge = -1;                       
                         int                                     activeLength = 0;                       
                                   
                         // remainingSuffixCount tells how many suffixes yet to                       
                         // be added in tree                       
                         int                                     remainingSuffixCount = 0;                       
                         int                                     leafEnd = -1;                       
                         int                                     *rootEnd = NULL;                       
                         int                                     *splitEnd = NULL;                       
                         int                                     size = -1;                                     //Length of input string                       
                                   
                         Node *newNode(                                     int                                     start,                                     int                                     *end)                       
                         {                       
                                                 Node *node =(Node*)                                     malloc                                     (                                     sizeof                                     (Node));                       
                                                 int                                     i;                       
                                                 for                                     (i = 0; i < MAX_CHAR; i++)                       
                                                 node->children[i] = NULL;                       
                                   
                                                 /*For root node, suffixLink will be set to NULL                       
                                                 For internal nodes, suffixLink will be set to root                       
                                                 by default in  current extension and may change in                       
                                                 next extension*/                       
                                                 node->suffixLink = root;                       
                                                 node->start = start;                       
                                                 node->end = end;                       
                                   
                                                 /*suffixIndex will be set to -1 by default and                       
                                                 actual suffix index will be set later for leaves                       
                                                 at the end of all phases*/                       
                                                 node->suffixIndex = -1;                       
                                                 return                                     node;                       
                         }                       
                                   
                         int                                     edgeLength(Node *n) {                       
                                                 if                                     (n == root)                       
                                                 return                                     0;                       
                                                 return                                     *(n->end) - (n->start) + 1;                       
                         }                       
                                   
                         int                                     walkDown(Node *currNode)                       
                         {                       
                                                 /*activePoint change for walk down (APCFWD) using                       
                                                 Skip/Count Trick  (Trick 1). If activeLength is greater                       
                                                 than current edge length, set next  internal node as                       
                                                 activeNode and adjust activeEdge and activeLength                       
                                                 accordingly to represent same activePoint*/                       
                                                 if                                     (activeLength >= edgeLength(currNode))                       
                                                 {                       
                                                 activeEdge += edgeLength(currNode);                       
                                                 activeLength -= edgeLength(currNode);                       
                                                 activeNode = currNode;                       
                                                 return                                     1;                       
                                                 }                       
                                                 return                                     0;                       
                         }                       
                                   
                         void                                     extendSuffixTree(                                     int                                     pos)                       
                         {                       
                                                 /*Extension Rule 1, this takes care of extending all                       
                                                 leaves created so far in tree*/                       
                                                 leafEnd = pos;                       
                                   
                                                 /*Increment remainingSuffixCount indicating that a                       
                                                 new suffix added to the list of suffixes yet to be                       
                                                 added in tree*/                       
                                                 remainingSuffixCount++;                       
                                   
                                                 /*set lastNewNode to NULL while starting a new phase,                       
                                                 indicating there is no internal node waiting for                       
                                                 it's suffix link reset in current phase*/                       
                                                 lastNewNode = NULL;                       
                                   
                                                 //Add all suffixes (yet to be added) one by one in tree                       
                                                 while                                     (remainingSuffixCount > 0) {                       
                                   
                                                 if                                     (activeLength == 0)                       
                                                 activeEdge = pos;                                     //APCFALZ                       
                                   
                                                 // There is no outgoing edge starting with                       
                                                 // activeEdge from activeNode                       
                                                 if                                     (activeNode->children] == NULL)                       
                                                 {                       
                                                 //Extension Rule 2 (A new leaf edge gets created)                       
                                                 activeNode->children] =                       
                                                 newNode(pos, &leafEnd);                       
                                   
                                                 /*A new leaf edge is created in above line starting                       
                                                 from  an existing node (the current activeNode), and                       
                                                 if there is any internal node waiting for it's suffix                       
                                                 link get reset, point the suffix link from that last                       
                                                 internal node to current activeNode. Then set lastNewNode                       
                                                 to NULL indicating no more node waiting for suffix link                       
                                                 reset.*/                       
                                                 if                                     (lastNewNode != NULL)                       
                                                 {                       
                                                 lastNewNode->suffixLink = activeNode;                       
                                                 lastNewNode = NULL;                       
                                                 }                       
                                                 }                       
                                                 // There is an outgoing edge starting with activeEdge                       
                                                 // from activeNode                       
                                                 else                       
                                                 {                       
                                                 // Get the next node at the end of edge starting                       
                                                 // with activeEdge                       
                                                 Node *next = activeNode->children];                       
                                                 if                                     (walkDown(next))                                     //Do walkdown                       
                                                 {                       
                                                 //Start from next node (the new activeNode)                       
                                                 continue                                     ;                       
                                                 }                       
                                                 /*Extension Rule 3 (current character being processed                       
                                                 is already on the edge)*/                       
                                                 if                                     (text[next->start + activeLength] == text[pos])                       
                                                 {                       
                                                 //If a newly created node waiting for it's                       
                                                 //suffix link to be set, then set suffix link                       
                                                 //of that waiting node to current active node                       
                                                 if                                     (lastNewNode != NULL && activeNode != root)                       
                                                 {                       
                                                 lastNewNode->suffixLink = activeNode;                       
                                                 lastNewNode = NULL;                       
                                                 }                       
           
                                                 //APCFER3                       
                                                 activeLength++;                       
                                                 /*STOP all further processing in this phase                       
                                                 and move on to next phase*/                       
                                                 break                                     ;                       
                                                 }                       
                                   
                                                 /*We will be here when activePoint is in middle of                       
                                                 the edge being traversed and current character                       
                                                 being processed is not  on the edge (we fall off                       
                                                 the tree). In this case, we add a new internal node                       
                                                 and a new leaf edge going out of that new node. This                       
                                                 is Extension Rule 2, where a new leaf edge and a new                       
                                                 internal node get created*/                       
                                                 splitEnd = (                                     int                                     *)                                     malloc                                     (                                     sizeof                                     (                                     int                                     ));                       
                                                 *splitEnd = next->start + activeLength - 1;                       
                                   
                                                 //New internal node                       
                                                 Node *split = newNode(next->start, splitEnd);                       
                                                 activeNode->children] = split;                       
                                   
                                                 //New leaf coming out of new internal node                       
                                                 split->children] = newNode(pos, &leafEnd);                       
                                                 next->start += activeLength;                       
                                                 split->children] = next;                       
                                   
                                                 /*We got a new internal node here. If there is any                       
                                                 internal node created in last extensions of same                       
                                                 phase which is still waiting for it's suffix link                       
                                                 reset, do it now.*/                       
                                                 if                                     (lastNewNode != NULL)                       
                                                 {                       
                                                 /*suffixLink of lastNewNode points to current newly                       
                                                 created internal node*/                       
                                                 lastNewNode->suffixLink = split;                       
                                                 }                       
                                   
                                                 /*Make the current newly created internal node waiting                       
                                                 for it's suffix link reset (which is pointing to root                       
                                                 at present). If we come across any other internal node                       
                                                 (existing or newly created) in next extension of same                       
                                                 phase, when a new leaf edge gets added (i.e. when                       
                                                 Extension Rule 2 applies is any of the next extension                       
                                                 of same phase) at that point, suffixLink of this node                       
                                                 will point to that internal node.*/                       
                                                 lastNewNode = split;                       
                                                 }                       
                                   
                                                 /* One suffix got added in tree, decrement the count of                       
                                                 suffixes yet to be added.*/                       
                                                 remainingSuffixCount--;                       
                                                 if                                     (activeNode == root && activeLength > 0)                                     //APCFER2C1                       
                                                 {                       
                                                 activeLength--;                       
                                                 activeEdge = pos - remainingSuffixCount + 1;                       
                                                 }                       
                                                 else                                     if                                     (activeNode != root)                                     //APCFER2C2                       
                                                 {                       
                                                 activeNode = activeNode->suffixLink;                       
                                                 }                       
                                                 }                       
                         }                       
                                   
                         void                                     print(                                     int                                     i,                                     int                                     j)                       
                         {                       
                                                 int                                     k;                       
                                                 for                                     (k=i; k<=j && text[k] !=                                     '#'                                     ; k++)                       
                                                 printf                                     (                                     "%c"                                     , text[k]);                       
                                                 if                                     (k<=j)                       
                                                 printf                                     (                                     "#"                                     );                       
                         }                       
                                   
                         //Print the suffix tree as well along with setting suffix index                       
                         //So tree will be printed in DFS manner                       
                         //Each edge along with it's suffix index will be printed                       
                         void                                     setSuffixIndexByDFS(Node *n,                                     int                                     labelHeight)                       
                         {                       
                                                 if                                     (n == NULL)                                     return                                     ;                       
                                   
                                                 if                                     (n->start != -1)                                     //A non-root node                       
                                                 {                       
                                                 //Print the label on edge from parent to current node                       
                                                 print(n->start, *(n->end));                       
                                                 }                       
                                                 int                                     leaf = 1;                       
                                                 int                                     i;                       
                                                 for                                     (i = 0; i < MAX_CHAR; i++)                       
                                                 {                       
                                                 if                                     (n->children[i] != NULL)                       
                                                 {                       
                                                 if                                     (leaf == 1 && n->start != -1)                       
                                                 printf                                     (                                     " [%d]"                                     , n->suffixIndex);                       
                                   
                                                 //Current node is not a leaf as it has outgoing                       
                                                 //edges from it.                       
                                                 leaf = 0;                       
                                                 setSuffixIndexByDFS(n->children[i], labelHeight +                       
                                                 edgeLength(n->children[i]));                       
                                                 }                       
                                                 }                       
                                                 if                                     (leaf == 1)                       
                                                 {                       
                                                 for                                     (i= n->start; i<= *(n->end); i++)                       
                                                 {                       
                                                 if                                     (text[i] ==                                     '#'                                     )                                     //Trim unwanted characters                       
                                                 {                       
                                                 n->end = (                                     int                                     *)                                     malloc                                     (                                     sizeof                                     (                                     int                                     ));                       
                                                 *(n->end) = i;                       
                                                 }                       
                                                 }                       
                                                 n->suffixIndex = size - labelHeight;                       
                                                 printf                                     (                                     " [%d]"                                     , n->suffixIndex);                       
                                                 }                       
                         }                       
                                   
                         void                                     freeSuffixTreeByPostOrder(Node *n)                       
                         {                       
                                                 if                                     (n == NULL)                       
                                                 return                                     ;                       
                                                 int                                     i;                       
                                                 for                                     (i = 0; i < MAX_CHAR; i++)                       
                                                 {                       
                                                 if                                     (n->children[i] != NULL)                       
                                                 {                       
                                                 freeSuffixTreeByPostOrder(n->children[i]);                       
                                                 }                       
                                                 }                       
                                                 if                                     (n->suffixIndex == -1)                       
                                                 free                                     (n->end);                       
                                                 free                                     (n);                       
                         }                       
                                   
                         /*Build the suffix tree and print the edge labels along with                       
                         suffixIndex. suffixIndex for leaf edges will be >= 0 and                       
                         for non-leaf edges will be -1*/                       
                         void                                     buildSuffixTree()                       
                         {                       
                                                 size =                                     strlen                                     (text);                       
                                                 int                                     i;                       
                                                 rootEnd = (                                     int                                     *)                                     malloc                                     (                                     sizeof                                     (                                     int                                     ));                       
                                                 *rootEnd = - 1;                       
                                   
                                                 /*Root is a special node with start and end indices as -1,                       
                                                 as it has no parent from where an edge comes to root*/                       
                                                 root = newNode(-1, rootEnd);                       
                                   
                                                 activeNode = root;                                     //First activeNode will be root                       
                                                 for                                     (i=0; i<size; i++)                       
                                                 extendSuffixTree(i);                       
                                                 int                                     labelHeight = 0;                       
                                                 setSuffixIndexByDFS(root, labelHeight);                       
                                   
                                                 //Free the dynamically allocated memory                       
                                                 freeSuffixTreeByPostOrder(root);                       
                         }                       
                                   
                         // driver program to test above functions                       
                         int                                     main(                                     int                                     argc,                                     char                                     *argv[])                       
                         {                       
                         //  strcpy(text, "xabxac#abcabxabcd$"); buildSuffixTree();                       
                                                 strcpy                                     (text,                                     "xabxa#babxba$"                                     ); buildSuffixTree();                       
                                                 return                                     0;                       
                         }                       

输出：（你可以看到下面的输出对应于2 ^钕上图）

# [5]$ [12]a [-1]# [4]$ [11]bx [-1]a# [1]ba$ [7]b [-1]a [-1]$ [10]bxba$ [6]x [-1]a# [2]ba$ [8]x [-1]a [-1]# [3]bxa# [0]ba$ [9]

如果两个字符串的大小分别为M和N，那么这个实现将占用O（M+N）的时间和空间。如果输入字符串尚未连接，则总共需要2个（M+N）空间，M+N空间用于存储广义后缀树，另一个M+N空间用于存储连接的字符串。

后续行动： 将上述实现扩展到两个以上的字符串（即，使用唯一的终端符号连接所有字符串，然后为连接的字符串构建后缀树）这种方法的一个问题是每个输入字符串都需要唯一的终端符号。这将适用于少数字符串，但如果有太多的输入字符串，我们可能无法找到许多唯一的终端符号。我们将很快讨论另一种构建通用后缀树的方法，我们只需要一个唯一的终端符号，这将解决上述问题，并可用于为任意数量的输入字符串构建通用后缀树。

我们发表了以下更多关于后缀树应用程序的文章：

本文由导演。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章