从Trie树谈到后缀树之后缀树的C++简单实现_数据分析师

本程序只是简单实现了后缀树的构造，查询等基本的操作。如果此文能引出读者更好的suffixtree 的实现，此文的价值便更甚了。谢谢。

suffix-tree的c++实现

    完整源码如下，由于注释已经够详细，便不再多说什么了：

1. // suffer tree.cpp : 定义控制台应用程序的入口点。
2. //copyright@ 2011 July && 匿名
4. //1、参考了他人的程序，但不知道原作者是谁。
5. //如果你知道，请立马联系我，一定把原作者的大名署上，谢谢。
6. //2、主函数没有写全了，读者视需要自己补上吧。
8. #include "stdafx.h"
9. #ifndef __SUFFIXTREE_H
10. #define __SUFFIXTREE_H
11. #include 
12. #include 
13. #include 
14. usingnamespacestd;
15. usingstd::list;
16. usingstd::vector;
18. //对于叶节点,通过m_nActiveLen和m_nEdgeLabelEndPos可以得到节点对应的字符串.对于分支节点,也是如此.
19. structtagSuffixNode
20. {
21. public:
22. tagSuffixNode* m_tpChild;//子节点,如果为0,说明是叶子节点
23. tagSuffixNode* m_tpParent;//父节点,根节点的父节点为0
24. tagSuffixNode* m_tpLeftSibling;//左兄弟
25. tagSuffixNode* m_tpRightSibling;//右兄弟
26. tagSuffixNode* m_tpMostRightChild;//最右子节点
27. tagSuffixNode* m_tpSuffixLink;//指向当前节点表示的子串的最大后缀所对应的分支节点
29. intm_nActiveLen;//节点代表的字符串的长度.
30. intm_nEdgeLabelStartPos;//入边开始字符的下标.对于分支节点,只是用来表示边对应的字符串是什么,并不表示其在子孙叶节点表示的串中对应位置的字符在整个串中的下标.
31. intm_nEdgeLabelEndPos;//入边结束字符的下标
32. boolm_bIsLeaf;//是否是叶节点
34. charm_cIndex;//test
36. public:
37. //全部初始化为0
38. voidinit()
39. {
40. m_tpChild = 0;
41. m_tpParent = 0;
42. m_tpLeftSibling = 0;
43. m_tpRightSibling = 0;
44. m_tpMostRightChild = 0;
45. m_tpSuffixLink = 0;
47. m_nEdgeLabelStartPos = 0;
48. m_nEdgeLabelEndPos = 0;
50. m_nActiveLen = 0;
51. m_bIsLeaf =true;
52. }
53. };
55. classCSuffixTree
56. {
57. public:
58. CSuffixTree(char*str);
59. ~CSuffixTree();
60. voiddeleteTree();
61. voidconstruct();
62. voidreset(char*str);
63. intsearch(char*str);
64. tagSuffixNode* getTree();
65. voidprintTree();
66. voidtest();
67. private:
68. tagSuffixNode* __allocNode();
69. tagSuffixNode* __findChildBeginWithChar(tagSuffixNode* node,charc);
71. void__printHelper(tagSuffixNode* node,intlevel);
72. private:
73. intm_nActiveLen;
74. intm_nStrLen;//字符串长度
75. tagSuffixNode* m_tpRoot;//根节点
76. tagSuffixNode* m_tpActiveNode;//活动节点
77. char*m_cpInternalStr;//字符串内存存储
79. list m_tagNodeList;//保存分配的节点的指针
80. vector m_tagFromNodeVec;//保存还未确定后缀指针的分支节点的指针，用于判定suffix link
81. vector m_tagToNodeVec;//保存所有分支节点
82. #ifdef DEBUG
83. charm_cIndex;
84. #endif
85. };
87. #endif //
89. //#include "suffixtree.h"
90. #include 
91. #include 
92. #include 
93. #include 
94. #include 
95. usingnamespacestd;
97. CSuffixTree::CSuffixTree(char*str)
98. :m_nActiveLen(0),
99. m_tpRoot(0),
100. m_tpActiveNode(0)
101. {
102. m_nStrLen = strlen(str) + 1;
103. m_cpInternalStr =newchar[m_nStrLen+1];
105. sprintf(m_cpInternalStr,"%s#", str);
106. #ifdef DEBUG
107. m_cIndex ='A';
108. #endif
109. }
111. CSuffixTree::~CSuffixTree()
112. {
113. deleteTree();
114. delete[] m_cpInternalStr;
115. }
117. voidCSuffixTree::deleteTree()
118. {
119. list::iterator iter = m_tagNodeList.begin();
120. for(; iter != m_tagNodeList.end(); ++iter)
121. {
122. delete*iter;
123. }
125. m_tagNodeList.clear();
126. }
128. voidCSuffixTree::reset(char*str)
129. {
130. deleteTree();
132. inttmp = strlen(str);
133. if(tmp+1 > m_nStrLen)
134. {
135. m_nStrLen = tmp+1;
136. delete[] m_cpInternalStr;
137. m_cpInternalStr =newchar[m_nStrLen+1];
138. }
139. else
140. {
141. m_nStrLen = tmp+1;
142. }
143. sprintf(m_cpInternalStr,"%s#", str);
145. m_nActiveLen = 0;
146. m_nStrLen = 0;
147. m_tpActiveNode = 0;
148. m_tpRoot = 0;
150. m_tagFromNodeVec.clear();
151. //reconstruct tree for new string
152. construct();
153. }
156. //suffixTree之构造
157. voidCSuffixTree::construct()
158. {
159. m_tpRoot = __allocNode();
160. if(m_tpRoot == 0)
161. {
162. #ifdef DEBUG
163. printf("__allocNode error!\n");
164. #endif
165. return;
166. }
167. m_nActiveLen = 0;
168. m_tpRoot->m_nActiveLen = 0;
169. //initial active node
170. m_tpActiveNode = m_tpRoot;
172. m_tagToNodeVec.push_back(m_tpRoot);
174. for(inti = 0; i
175. {
176. #ifdef DEBUG
177. printf("\ninsert %s\n", &(m_cpInternalStr[i]));
178. printf("active node:[%c]\n", m_tpActiveNode->m_cIndex);
179. #endif
180. //判断是否有后继节点
181. if(m_tpActiveNode->m_tpSuffixLink != 0)
182. {
183. m_tpActiveNode = m_tpActiveNode->m_tpSuffixLink;
184. m_nActiveLen--;
185. }
186. intpos = i;
188. #ifdef DEBUG
189. printf("new active node:[%c]\n", m_tpActiveNode->m_cIndex);
190. printf("pos:%d\n", pos);
191. printf("active length:%d\n", m_nActiveLen);
192. #endif
194. while(true)
195. {
196. //查找以当前后缀串的开始字符开始的子节点
197. tagSuffixNode* node = __findChildBeginWithChar(m_tpActiveNode, m_cpInternalStr[i+m_nActiveLen]);
198. //未找到以suffix[i]的开始字符开头的节点
199. if(node == 0)
200. {
201. #ifdef DEBUG
202. printf("__findChildBeginWithChar null\n");
203. #endif
204. tagSuffixNode* child = __allocNode();
206. //设置开始、结束位置的下标
207. child->m_nEdgeLabelStartPos = pos;
208. child->m_nEdgeLabelEndPos = m_nStrLen-1;
209. //设置叶节点代表的后缀串的长度
210. child->m_nActiveLen = m_nStrLen - i;
211. //设置父节点
212. child->m_tpParent = m_tpActiveNode;
213. if( m_tpActiveNode->m_tpChild == 0)
214. {
215. m_tpActiveNode->m_tpChild = child;
216. m_tpActiveNode->m_tpMostRightChild = child;
217. }
218. else
219. {
220. m_tpActiveNode->m_tpMostRightChild->m_tpRightSibling = child;
221. child->m_tpLeftSibling = m_tpActiveNode->m_tpMostRightChild;
222. m_tpActiveNode->m_tpMostRightChild = child;
223. }
225. break;
226. }
227. else
228. {
229. #ifdef DEBUG
230. printf("__findChildBeginWithChar ok\n");
231. printf("node start:%d\n", node->m_nEdgeLabelStartPos);
232. printf("node end:%d\n", node->m_nEdgeLabelEndPos);
233. printf("node index:%c\n", node->m_cIndex);
234. #endif
235. //TODO
236. //确定 m_nMinDistance
237. intedgeStart = node->m_nEdgeLabelStartPos;
238. intstrStart = i + m_nActiveLen;
239. boolsplit =false;
241. for(; edgeStart<=node->m_nEdgeLabelEndPos; edgeStart++, strStart++)
242. {
243. if( m_cpInternalStr[edgeStart] != m_cpInternalStr[strStart])
244. {
245. split =true;
246. break;
247. }
248. }
249. if(!split)
250. {
251. m_tpActiveNode = node;
252. m_nActiveLen += node->m_nEdgeLabelEndPos - node->m_nEdgeLabelStartPos + 1;
253. pos += node->m_nEdgeLabelEndPos - node->m_nEdgeLabelStartPos + 1;
254. continue;
255. }
256. else
257. {
258. tagSuffixNode* parent = node->m_tpParent;
259. //new branch node
260. tagSuffixNode* branch = __allocNode();
261. branch->m_bIsLeaf =false;
262. branch->m_nEdgeLabelStartPos = node->m_nEdgeLabelStartPos;
263. branch->m_nEdgeLabelEndPos = edgeStart-1;
264. branch->m_nActiveLen = parent->m_nActiveLen + (branch->m_nEdgeLabelEndPos - branch->m_nEdgeLabelStartPos + 1);
265. //original node
266. node->m_nEdgeLabelStartPos = edgeStart;
268. tagSuffixNode* info = __allocNode();
269. info->m_nEdgeLabelStartPos = strStart;
270. info->m_nEdgeLabelEndPos = m_nStrLen - 1;
271. info->m_nActiveLen = branch->m_nActiveLen + (info->m_nEdgeLabelEndPos - info->m_nEdgeLabelStartPos + 1);
273. branch->m_tpParent = parent;
274. branch->m_tpRightSibling = parent->m_tpChild;
275. parent->m_tpChild->m_tpLeftSibling = branch;
276. parent->m_tpChild = branch;
278. node->m_tpLeftSibling->m_tpRightSibling = node->m_tpRightSibling;
279. if( node->m_tpRightSibling != 0)
280. {
281. node->m_tpRightSibling->m_tpLeftSibling = node->m_tpLeftSibling;
282. }
283. else
284. {
285. parent->m_tpMostRightChild = node->m_tpLeftSibling;
286. }
288. branch->m_tpChild = info;
289. branch->m_tpMostRightChild = node;
291. info->m_tpRightSibling = node;
292. info->m_tpParent = branch;
294. node->m_tpParent = branch;
295. node->m_tpLeftSibling = info;
296. node->m_tpRightSibling = 0;
299. //设置节点的suffix link
301. boolsetSuffix =false;
302. vector::iterator iter = m_tagToNodeVec.begin();
303. for(; iter != m_tagToNodeVec.end(); ++iter)
304. {
305. tagSuffixNode* tmp = *iter;
306. if( strncmp( &(m_cpInternalStr[branch->m_nEdgeLabelEndPos - branch->m_nActiveLen + 2]), &(m_cpInternalStr[tmp->m_nEdgeLabelEndPos - tmp->m_nActiveLen + 1]), branch->m_nActiveLen - 1) == 0)
307. {
308. branch->m_tpSuffixLink = tmp;
309. setSuffix =true;
310. break;
311. #ifdef DEBUG
312. printf("branch[%c] suffix_link is branch[%c]\n", tmp->m_cIndex, branch->m_cIndex);
313. #endif
314. }
315. }
316. m_tagToNodeVec.push_back(branch);
318. vector::iterator iter2 = m_tagFromNodeVec.begin();
319. for(; iter2 != m_tagFromNodeVec.end(); ++iter2)
320. {
321. tagSuffixNode* tmp = *iter2;
322. //找到后缀节点，结束循环
323. if( strncmp( &(m_cpInternalStr[tmp->m_nEdgeLabelEndPos - tmp->m_nActiveLen + 2]), &(m_cpInternalStr[branch->m_nEdgeLabelEndPos - branch->m_nActiveLen + 1]), tmp->m_nActiveLen - 1) == 0)
324. {
325. tmp->m_tpSuffixLink = branch;
326. m_tagFromNodeVec.erase(iter2);
327. #ifdef DEBUG
328. printf("branch[%c] suffix_link is branch[%c]\n", tmp->m_cIndex, branch->m_cIndex);
329. #endif
330. break;
331. }
332. }
334. if( !setSuffix )
335. {
336. m_tagFromNodeVec.push_back(branch);
337. }
339. //已经将新的后缀字符串插入到树中，这时可以结束while了。
340. break;
341. }
342. }
343. }
344. //test
345. #ifdef DEBUG
346. printf("print\n");
347. printTree();
348. #endif
349. }
350. }
353. //查询
354. intCSuffixTree::search(char*str)
355. {
356. if(str == 0)
357. return-1;
358. //TODO
359. //添加处理过程
361. intlen = strlen(str);
363. tagSuffixNode* node = 0;
364. tagSuffixNode* cur = m_tpRoot;
365. for(inti=0; i
366. {
367. node = __findChildBeginWithChar(cur, str[i]);
368. if(node == 0)
369. {
370. break;
371. }
372. else
373. {
374. intedgeLen = node->m_nEdgeLabelEndPos - node->m_nEdgeLabelStartPos + 1;
375. intremain = len - i;
376. if( remain <= edgeLen )
377. {
378. if( strncmp(&(str[i]), &(m_cpInternalStr[node->m_nEdgeLabelStartPos]), remain) != 0)
379. {
380. return-1;
381. }
382. else
383. {
384. returnnode->m_nEdgeLabelEndPos - node->m_nActiveLen + 1;
385. }
386. }
387. else
388. {
389. if( strncmp(&(str[i]), &(m_cpInternalStr[node->m_nEdgeLabelStartPos]), edgeLen) != 0)
390. {
391. return-1;
392. }
393. else
394. {
395. i += edgeLen;
396. cur = node;
397. }
398. }
399. }
400. }
401. return-1;
402. }
404. tagSuffixNode* CSuffixTree::__allocNode()
405. {
406. tagSuffixNode* node =newtagSuffixNode;
408. m_tagNodeList.push_back(node);
410. node->init();
411. #ifdef DEBUG
412. node->m_cIndex = m_cIndex;
413. m_cIndex++;
414. #endif
415. returnnode;
416. }
418. tagSuffixNode* CSuffixTree::__findChildBeginWithChar(tagSuffixNode* node,charc)
419. {
420. assert(node != 0);
422. tagSuffixNode* child = node->m_tpChild;
423. while(child != 0)
424. {
425. if( m_cpInternalStr[child->m_nEdgeLabelStartPos] == c)
426. returnchild;
428. child = child->m_tpRightSibling;
429. }
431. return0;
432. }
434. voidCSuffixTree::test()
435. {
436. //printf("%s\n", m_cpInternalStr);
437. printTree();
438. }
440. voidCSuffixTree::printTree()
441. {
442. #ifdef DEBUG
443. printf("[A]\n");
444. #endif
445. __printHelper(m_tpRoot, 0);
446. }
448. voidCSuffixTree::__printHelper(tagSuffixNode* node,intlevel)
449. {
450. intstart = node->m_nEdgeLabelStartPos;
451. intend = node->m_nEdgeLabelEndPos;
452. tagSuffixNode* child = node->m_tpChild;
453. if( level > 0 )
454. {
455. for(inti=0; i
456. {
457. printf(" |");
458. }
459. printf(" + ");
460. for(intj = start; j <= end; j++)
461. {
462. printf("%c", m_cpInternalStr[j]);
463. }
464. #ifdef DEBUG
465. printf("[%c]", node->m_cIndex);
466. //         printf("[%d:%d:%d]", node->m_nEdgeLabelStartPos, node->m_nEdgeLabelEndPos, node->m_nActiveLen);
467. #endif
468. printf("\n");
469. }
471. while( child != 0 )
472. {
473. __printHelper(child, level+1);
474. child = child->m_tpRightSibling;
475. }
476. }
478. intmain()
479. {
480. cout<<"hello suffixtree"<
481. system("pause");
482. return0;
483. }

    运行结果如下：

Shlomo Yona的实现

    下面是国外一牛人Shlomo Yona写的实现（摘取了部分非完整代码）：

1. /******************************************************************************
2. Suffix Tree Version 2.1
4. AUTHORS
6. Dotan Tsadok
7. Instructor: Mr. Shlomo Yona, University of Haifa, Israel. December 2002.
8. Current maintainer: Shlomo Yona 
10. COPYRIGHT
12. Copyright 2002-2003 Shlomo Yona
14. LICENSE
16. This library is free software; you can redistribute it and/or modify it
17. under the same terms as Perl itself.
20. DESCRIPTION OF THIS FILE:
22. This is the implementation file suffix_tree.c implementing the header file
23. suffix_tree.h.
25. This code is an Open Source implementation of Ukkonen's algorithm for
26. constructing a suffix tree over a string in time and space complexity
27. O(length of the string). The code is written under strict ANSI C.
29. For a complete understanding of the code see Ukkonen's algorithm and the
30. readme.txt file.
32. The general pseudo code is:
34. n = length of the string.
35. ST_CreateTree:
36. Calls n times to SPA (Single Phase Algorithm). SPA:
37. Increase the variable e (virtual end of all leaves).
38. Calls SEA (Single Extension Algorithm) starting with the first extension that
39. does not already exist in the tree and ending at the first extension that
40. already exists. SEA :
41. Follow suffix link.
42. Check if current suffix exists in the tree.
43. If it does not - apply rule 2 and then create a new suffix link.
44. apply_rule_2:
45. Create a new leaf and maybe a new internal node as well.
46. create_node:
47. Create a new node or a leaf.
50. For implementation interpretations see Basic Ideas paragraph in the Developement
51. section of the readme.txt file.
53. An example of the implementations of a node and its sons using linked lists
54. instead of arrays:
56. (1)
57. |
58. |
59. |
60. (2)--(3)--(4)--(5)
62. (2) is the only son of (1) (call it the first son). Other sons of (1) are
63. connected using a linked lists starting from (2) and going to the right. (3) is
64. the right sibling of (2) (and (2) is the left sibling of (3)), (4) is the right
65. sibling of (3), etc.
66. The father field of all (2), (3), (4) and (5) points to (1), but the son field
67. of (1) points only to (2).
69. *******************************************************************************/
71. #include "stdlib.h"
72. #include "stdio.h"
73. #include "string.h"
74. #include "suffix_tree.h"
76. /* See function body */
77. voidST_PrintTree(SUFFIX_TREE* tree);
78. /* See function body */
79. voidST_PrintFullNode(SUFFIX_TREE* tree, NODE* node);
81. /* Used in function trace_string for skipping (Ukkonen's Skip Trick). */
82. typedefenumSKIP_TYPE     {skip, no_skip}                 SKIP_TYPE;
83. /* Used in function apply_rule_2 - two types of rule 2 - see function for more
84. details.*/
85. typedefenumRULE_2_TYPE   {new_son, split}                RULE_2_TYPE;
86. /* Signals whether last matching position is the last one of the current edge */
87. typedefenumLAST_POS_TYPE {last_char_in_edge, other_char} LAST_POS_TYPE;
89. /* Used for statistic measures of speed. */
90. DBL_WORD counter;
91. /* Used for statistic measures of space. */
92. DBL_WORD heap;
93. /* Used to mark the node that has no suffix link yet. By Ukkonen, it will have
94. one by the end of the current phase. */
95. NODE*    suffixless;
97. typedefstructSUFFIXTREEPATH
98. {
99. DBL_WORD   begin;
100. DBL_WORD   end;
101. } PATH;
103. typedefstructSUFFIXTREEPOS
104. {
105. NODE*      node;
106. DBL_WORD   edge_pos;
107. }POS;
109. /******************************************************************************/
110. /*
111. Define STATISTICS in order to view measures of speed and space while
112. constructing and searching the suffix tree. Measures will be printed on the
113. screen.
114. */
115. /* #define STATISTICS */
117. /*
118. Define DEBUG in order to view debug printouts to the screen while
119. constructing and searching the suffix tree.
120. */
121. /* #define DEBUG */
123. /******************************************************************************/
124. /*
125. create_node :
126. Creates a node with the given init field-values.
128. Input : The father of the node, the starting and ending indices
129. of the incloming edge to that node,
130. the path starting position of the node.
132. Output: A pointer to that node.
133. */
136. NODE* create_node(NODE* father, DBL_WORD start, DBL_WORD end, DBL_WORD position)
137. {
138. /*Allocate a node.*/
139. NODE* node   = (NODE*)malloc(sizeof(NODE));
140. if(node == 0)
141. {
142. printf("\nOut of memory.\n");
143. exit(0);
144. }
146. #ifdef STATISTICS
147. heap+=sizeof(NODE);
148. #endif
150. /* Initialize node fields. For detailed description of the fields see
151. suffix_tree.h */
152. node->sons             = 0;
153. node->right_sibling    = 0;
154. node->left_sibling     = 0;
155. node->suffix_link      = 0;
156. node->father           = father;
157. node->path_position    = position;
158. node->edge_label_start = start;
159. node->edge_label_end   = end;
160. returnnode;
161. }
163. /******************************************************************************/
164. /*
165. find_son :
166. Finds son of node that starts with a certain character.
168. Input : the tree, the node to start searching from and the character to be
169. searched in the sons.
171. Output: A pointer to the found son, 0 if no such son.
172. */
174. NODE* find_son(SUFFIX_TREE* tree, NODE* node,charcharacter)
175. {
176. /* Point to the first son. */
177. node = node->sons;
178. /* scan all sons (all right siblings of the first son) for their first
179. character (it has to match the character given as input to this function. */
180. while(node != 0 && tree->tree_string[node->edge_label_start] != character)
181. {
182. #ifdef STATISTICS
183. counter++;
184. #endif
185. node = node->right_sibling;
186. }
187. returnnode;
188. }
190. /******************************************************************************/
191. /*
192. get_node_label_end :
193. Returns the end index of the incoming edge to that node. This function is
194. needed because for leaves the end index is not relevant, instead we must look
195. at the variable "e" (the global virtual end of all leaves). Never refer
196. directly to a leaf's end-index.
198. Input : the tree, the node its end index we need.
200. Output: The end index of that node (meaning the end index of the node's
201. incoming edge).
202. */
204. DBL_WORD get_node_label_end(SUFFIX_TREE* tree, NODE* node)
205. {
206. /* If it's a leaf - return e */
207. if(node->sons == 0)
208. returntree->e;
209. /* If it's not a leaf - return its real end */
210. returnnode->edge_label_end;
211. }
213. /******************************************************************************/
214. /*
215. get_node_label_length :
216. Returns the length of the incoming edge to that node. Uses get_node_label_end
217. (see above).
219. Input : The tree and the node its length we need.
221. Output: the length of that node.
222. */
224. DBL_WORD get_node_label_length(SUFFIX_TREE* tree, NODE* node)
225. {
226. /* Calculate and return the lentgh of the node */
227. returnget_node_label_end(tree, node) - node->edge_label_start + 1;
228. }
230. /******************************************************************************/
231. /*
232. is_last_char_in_edge :
233. Returns 1 if edge_pos is the last position in node's incoming edge.
235. Input : The tree, the node to be checked and the position in its incoming
236. edge.
238. Output: the length of that node.
239. */
241. charis_last_char_in_edge(SUFFIX_TREE* tree, NODE* node, DBL_WORD edge_pos)
242. {
243. if(edge_pos == get_node_label_length(tree,node)-1)
244. return1;
245. return0;
246. }
248. /******************************************************************************/
249. /*
250. connect_siblings :
251. Connect right_sib as the right sibling of left_sib and vice versa.
253. Input : The two nodes to be connected.
255. Output: None.
256. */
258. voidconnect_siblings(NODE* left_sib, NODE* right_sib)
259. {
260. /* Connect the right node as the right sibling of the left node */
261. if(left_sib != 0)
262. left_sib->right_sibling = right_sib;
263. /* Connect the left node as the left sibling of the right node */
264. if(right_sib != 0)
265. right_sib->left_sibling = left_sib;
266. }
268. /******************************************************************************/
269. /*
270. apply_extension_rule_2 :
271. Apply "extension rule 2" in 2 cases:
272. 1. A new son (leaf 4) is added to a node that already has sons:
273. (1)        (1)
274. /   \     ->   / | \
275. (2)  (3)      (2)(3)(4)
277. 2. An edge is split and a new leaf (2) and an internal node (3) are added:
278. |       |
279. |      (3)
280. |     ->   / \
281. (1)       (1) (2)
283. Input : See parameters.
285. Output: A pointer to the newly created leaf (new_son case) or internal node
286. (split case).
287. */
289. NODE* apply_extension_rule_2(
290. /* Node 1 (see drawings) */
291. NODE*           node,
292. /* Start index of node 2's incoming edge */
293. DBL_WORD        edge_label_begin,
294. /* End index of node 2's incoming edge */
295. DBL_WORD        edge_label_end,
296. /* Path start index of node 2 */
297. DBL_WORD        path_pos,
298. /* Position in node 1's incoming edge where split is to be
299. performed */
300. DBL_WORD        edge_pos,
301. /* Can be 'new_son' or 'split' */
302. RULE_2_TYPE     type)
303. {
304. NODE *new_leaf,
305. *new_internal,
306. *son;
307. /*-------new_son-------*/
308. if(type == new_son)
309. {
310. #ifdef DEBUG
311. printf("rule 2: new leaf (%lu,%lu)\n",edge_label_begin,edge_label_end);
312. #endif
313. /* Create a new leaf (4) with the characters of the extension */
314. new_leaf = create_node(node, edge_label_begin , edge_label_end, path_pos);
315. /* Connect new_leaf (4) as the new son of node (1) */
316. son = node->sons;
317. while(son->right_sibling != 0)
318. son = son->right_sibling;
319. connect_siblings(son, new_leaf);
320. /* return (4) */
321. returnnew_leaf;
322. }
323. /*-------split-------*/
324. #ifdef DEBUG
325. printf("rule 2: split (%lu,%lu)\n",edge_label_begin,edge_label_end);
326. #endif
327. /* Create a new internal node (3) at the split point */
328. new_internal = create_node(
329. node->father,
330. node->edge_label_start,
331. node->edge_label_start+edge_pos,
332. node->path_position);
333. /* Update the node (1) incoming edge starting index (it now starts where node
334. (3) incoming edge ends) */
335. node->edge_label_start += edge_pos+1;
337. /* Create a new leaf (2) with the characters of the extension */
338. new_leaf = create_node(
339. new_internal,
340. edge_label_begin,
341. edge_label_end,
342. path_pos);
344. /* Connect new_internal (3) where node (1) was */
345. /* Connect (3) with (1)'s left sibling */
346. connect_siblings(node->left_sibling, new_internal);
347. /* connect (3) with (1)'s right sibling */
348. connect_siblings(new_internal, node->right_sibling);
349. node->left_sibling = 0;
351. /* Connect (3) with (1)'s father */
352. if(new_internal->father->sons == node)
353. new_internal->father->sons = new_internal;
355. /* Connect new_leaf (2) and node (1) as sons of new_internal (3) */
356. new_internal->sons = node;
357. node->father = new_internal;
358. connect_siblings(node, new_leaf);
359. /* return (3) */
360. returnnew_internal;
361. }
363. /******************************************************************************/
364. /*
365. trace_single_edge :
366. Traces for a string in a given node's OUTcoming edge. It searches only in the
367. given edge and not other ones. Search stops when either whole string was
368. found in the given edge, a part of the string was found but the edge ended
369. (and the next edge must be searched too - performed by function trace_string)
370. or one non-matching character was found.
372. Input : The string to be searched, given in indices of the main string.
374. Output: (by value) the node where tracing has stopped.
375. (by reference) the edge position where last match occured, the string
376. position where last match occured, number of characters found, a flag
377. for signaling whether search is done, and a flag to signal whether
378. search stopped at a last character of an edge.
379. */
381. NODE* trace_single_edge(
382. SUFFIX_TREE*    tree,
383. /* Node to start from */
384. NODE*           node,
385. /* String to trace */
386. PATH            str,
387. /* Last matching position in edge */
388. DBL_WORD*       edge_pos,
389. /* Last matching position in tree source string */
390. DBL_WORD*       chars_found,
391. /* Skip or no_skip*/
392. SKIP_TYPE       type,
393. /* 1 if search is done, 0 if not */
394. int*            search_done)
395. {
396. NODE*      cont_node;
397. DBL_WORD   length,str_len;
399. /* Set default return values */
400. *search_done = 1;
401. *edge_pos    = 0;
403. /* Search for the first character of the string in the outcoming edge of
404. node */
405. cont_node = find_son(tree, node, tree->tree_string[str.begin]);
406. if(cont_node == 0)
407. {
408. /* Search is done, string not found */
409. *edge_pos = get_node_label_length(tree,node)-1;
410. *chars_found = 0;
411. returnnode;
412. }
414. /* Found first character - prepare for continuing the search */
415. node    = cont_node;
416. length  = get_node_label_length(tree,node);
417. str_len = str.end - str.begin + 1;
419. /* Compare edge length and string length. */
420. /* If edge is shorter then the string being searched and skipping is
421. enabled - skip edge */
422. if(type == skip)
423. {
424. if(length <= str_len)
425. {
426. (*chars_found)   = length;
427. (*edge_pos)      = length-1;
428. if(length < str_len)
429. *search_done  = 0;
430. }
431. else
432. {
433. (*chars_found)   = str_len;
434. (*edge_pos)      = str_len-1;
435. }
437. #ifdef STATISTICS
438. counter++;
439. #endif
441. returnnode;
442. }
443. else
444. {
445. /* Find minimum out of edge length and string length, and scan it */
446. if(str_len < length)
447. length = str_len;
449. for(*edge_pos=1, *chars_found=1; *edge_pos
450. {
452. #ifdef STATISTICS
453. counter++;
454. #endif
456. /* Compare current characters of the string and the edge. If equal -
457. continue */
458. if(tree->tree_string[node->edge_label_start+*edge_pos] != tree->tree_string[str.begin+*edge_pos])
459. {
460. (*edge_pos)--;
461. returnnode;
462. }
463. }
464. }
466. /* The loop has advanced *edge_pos one too much */
467. (*edge_pos)--;
469. if((*chars_found) < str_len)
470. /* Search is not done yet */
471. *search_done = 0;
473. returnnode;
474. }
476. /******************************************************************************/
477. /*
478. trace_string :
479. Traces for a string in the tree. This function is used in construction
480. process only, and not for after-construction search of substrings. It is
481. tailored to enable skipping (when we know a suffix is in the tree (when
482. following a suffix link) we can avoid comparing all symbols of the edge by
483. skipping its length immediately and thus save atomic operations - see
484. Ukkonen's algorithm, skip trick).
485. This function, in contradiction to the function trace_single_edge, 'sees' the
486. whole picture, meaning it searches a string in the whole tree and not just in
487. a specific edge.
489. Input : The string, given in indice of the main string.
491. Output: (by value) the node where tracing has stopped.
492. (by reference) the edge position where last match occured, the string
493. position where last match occured, number of characters found, a flag
494. for signaling whether search is done.
495. */
497. NODE* trace_string(
498. SUFFIX_TREE*    tree,
499. /* Node to start from */
500. NODE*           node,
501. /* String to trace */
502. PATH            str,
503. /* Last matching position in edge */
504. DBL_WORD*       edge_pos,
505. /* Last matching position in tree string */
506. DBL_WORD*       chars_found,
507. /* skip or not */
508. SKIP_TYPE       type)
509. {
510. /* This variable will be 1 when search is done.
511. It is a return value from function trace_single_edge */
512. intsearch_done = 0;
514. /* This variable will hold the number of matching characters found in the
515. current edge. It is a return value from function trace_single_edge */
516. DBL_WORD edge_chars_found;
518. *chars_found = 0;
520. while(search_done == 0)
521. {
522. *edge_pos        = 0;
523. edge_chars_found = 0;
524. node = trace_single_edge(tree, node, str, edge_pos, &edge_chars_found, type, &search_done);
525. str.begin       += edge_chars_found;
526. *chars_found    += edge_chars_found;
527. }
528. returnnode;
529. }
531. /******************************************************************************/
532. /*
533. ST_FindSubstring :
534. See suffix_tree.h for description.
535. */
537. DBL_WORD ST_FindSubstring(
538. /* The suffix array */
539. SUFFIX_TREE*    tree,
540. /* The substring to find */
541. char*  W,
542. /* The length of W */
543. DBL_WORD        P)
544. {
545. /* Starts with the root's son that has the first character of W as its
546. incoming edge first character */
547. NODE* node   = find_son(tree, tree->root, W[0]);
548. DBL_WORD k,j = 0, node_label_en