Ukkonen's algorithm - Revision history

Teafed: /* High level description of Ukkonen's algorithm */

2024-03-26T21:17:26Z

High level description of Ukkonen's algorithm

← Previous revision		Revision as of 21:17, 26 March 2024
Line 6:		Line 6:

	==High level description of Ukkonen's algorithm==		==High level description of Ukkonen's algorithm==
	Ukkonen's algorithm constructs an implicit suffix tree T{{sub\|i}} for each prefix S[1...i] of S (S being the string of length n). It first builds T{{sub\|1}} using 1{{sup\|st}} character, then T{{sub\|2}} using 2{{sup\|nd}} character, then T{{sub\|3}} using 3{{sup\|rd}} character, ..., T{{sub\|n}} using the n{{sup\|th}} character. You can find the following characteristics in a suffix tree that uses Ukkonen's algorithm:		Ukkonen's algorithm constructs an implicit suffix tree T{{sub\|i}} for each prefix S[1...i] of S (S being the string of length n). It first builds T{{sub\|1}} using the 1{{sup\|st}} character, then T{{sub\|2}} using the 2{{sup\|nd}} character, then T{{sub\|3}} using the 3{{sup\|rd}} character, ..., T{{sub\|n}} using the n{{sup\|th}} character. You can find the following characteristics in a suffix tree that uses Ukkonen's algorithm:

	* Implicit suffix tree T{{sub\|i+1}} is built on top of implicit suffix tree T{{sub\|i}} .		* Implicit suffix tree T{{sub\|i+1}} is built on top of implicit suffix tree T{{sub\|i}} .

Teafed: /* Ukkonen's algorithm example */

2024-03-26T20:34:22Z

Ukkonen's algorithm example

← Previous revision		Revision as of 20:34, 26 March 2024
Line 25:		Line 25:
	==Ukkonen's algorithm example==		==Ukkonen's algorithm example==
	[[File:Suffix Tree using Ukkonen's Algorithm.jpg\|thumb\|Final suffix tree using Ukkonen's algorithm (example).]]		[[File:Suffix Tree using Ukkonen's Algorithm.jpg\|thumb\|Final suffix tree using Ukkonen's algorithm (example).]]
	To better illustrate how a suffix tree using Ukkonen's algorithm ~~is constructed~~, we can ~~use~~ the ~~following~~ ~~example:~~		To better illustrate how a suffix tree is constructed using Ukkonen's algorithm, we can consider the string <code>S = xabxac</code>.

	S=xabxac

	# Start with an empty root node.		# Start with an empty root node.
	# Construct ~~T{{sub\|1}}~~ for S[1] by adding the first character of the string. Rule 2 applies, which creates a new leaf node.		# Construct <math>T_1</math> for <code>S[1]</code> by adding the first character of the string. Rule 2 applies, which creates a new leaf node.
	# Construct ~~T{{sub\|2}}~~ for S[1...2] by adding suffixes of xa (xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct <math>T_2</math> for <code>S[1..2]</code> by adding suffixes of <code>xa</code> (<code>xa</code> and <code>a</code>). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct ~~T{{sub\|3}}~~ for S[1...3] by adding suffixes of xab (xab, ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct <math>T_3</math> for <code>S[1..3]</code> by adding suffixes of <code>xab</code> (<code>xab</code>, <code>ab</code> and <code>b</code>). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct ~~T{{sub\|4}}~~ for S[1...4] by adding suffixes of xabx (xabx, abx, bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Construct <math>T_4</math> for <code>S[1..4]</code> by adding suffixes of <code>xabx</code> (<code>xabx</code>, <code>abx</code>, <code>bx</code> and <code>x</code>). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs ~~T{{sub\|5}}~~ for S[1...5] by adding suffixes of xabxa (xabxa, abxa, bxa, xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Constructs <math>T_5</math> for <code>S[1..5]</code> by adding suffixes of <code>xabxa</code> (<code>xabxa</code>, <code>abxa</code>, <code>bxa</code>, <code>xa</code> and <code>a</code>). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs ~~T{{sub\|6}}~~ for S[1...6] by adding suffixes of xabxac (xabxac, abxac, bxac, xac, ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new leaf edges and two new internal nodes are created).		# Constructs <math>T_6</math> for <code>S[1..6]</code> by adding suffixes of <code>xabxac</code> (<code>xabxac</code>, <code>abxac</code>, <code>bxac</code>, <code>xac</code>, <code>ac</code> and <code>c</code>). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new leaf edges and two new internal nodes are created).


	==References==		==References==

91.152.66.221: change lead edge to leaf edge (fix typo)

2023-08-23T12:48:09Z

change lead edge to leaf edge (fix typo)

← Previous revision		Revision as of 12:48, 23 August 2023
Line 35:		Line 35:
	# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx, abx, bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx, abx, bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa, abxa, bxa, xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa, abxa, bxa, xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac, abxac, bxac, xac, ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new ~~lead~~ edges and two new internal nodes are created).		# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac, abxac, bxac, xac, ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new leaf edges and two new internal nodes are created).

	==References==		==References==

Frap: /* Run time */

2023-05-15T23:37:22Z

Run time

← Previous revision		Revision as of 23:37, 15 May 2023
Line 21:		Line 21:

	==Run time==		==Run time==
	The naive implementation for generating a suffix tree going forward requires {{math\|''O''(''n''<sup>2</sup>)}} or even {{math\|''O''(''n''<sup>3</sup>)}} time complexity in [[big O notation]], where {{math\|''n''}} is the length of the string. By exploiting a number of algorithmic techniques, Ukkonen reduced this to {{math\|''O''(''n'')}} (linear) time, for constant-size alphabets, and {{math\|''O''(''n'' log ''n'')}} in general, matching the runtime performance of the earlier two algorithms.		The naive implementation for generating a suffix tree going forward requires {{math\|''O''(''n''<sup>2</sup>)}} or even {{math\|''O''(''n''<sup>3</sup>)}} time complexity in [[big O notation\|big ''O'' notation]], where {{math\|''n''}} is the length of the string. By exploiting a number of algorithmic techniques, Ukkonen reduced this to {{math\|''O''(''n'')}} (linear) time, for constant-size alphabets, and {{math\|''O''(''n'' log ''n'')}} in general, matching the runtime performance of the earlier two algorithms.

	==Ukkonen's algorithm example==		==Ukkonen's algorithm example==

Trikekus: fix typo(?)

2023-03-27T23:30:03Z

fix typo(?)

← Previous revision		Revision as of 23:30, 27 March 2023
Line 24:		Line 24:

	==Ukkonen's algorithm example==		==Ukkonen's algorithm example==
	[[File:Suffix Tree using Ukkonen's Algorithm.jpg\|thumb\|Final suffix ~~treen~~ using Ukkonen's algorithm (example).]]		[[File:Suffix Tree using Ukkonen's Algorithm.jpg\|thumb\|Final suffix tree using Ukkonen's algorithm (example).]]
	To better illustrate how a suffix tree using Ukkonen's algorithm is constructed, we can use the following example:		To better illustrate how a suffix tree using Ukkonen's algorithm is constructed, we can use the following example:

176.234.133.135: /* Ukkonen's algorithm example */

2023-03-20T18:42:37Z

Ukkonen's algorithm example

← Previous revision		Revision as of 18:42, 20 March 2023
Line 34:		Line 34:
	# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab (xab, ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab (xab, ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx, abx, bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx, abx, bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa, abxa, bxa, xa and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa, abxa, bxa, xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac, abxac, bxac, xac, ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).		# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac, abxac, bxac, xac, ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).

Loopology: /* External links */

2022-12-29T10:40:33Z

External links

← Previous revision		Revision as of 10:40, 29 December 2022
Line 42:		Line 42:
	==External links==		==External links==
	* [https://stackoverflow.com/a/9513423/414272 Detailed explanation in plain English]		* [https://stackoverflow.com/a/9513423/414272 Detailed explanation in plain English]
	* [~~http~~://marknelson.us/1996/08/01/suffix-trees/ Fast String Searching With Suffix Trees] Mark Nelson's tutorial. Has an implementation example written with C++.		* [https://marknelson.us/posts/1996/08/01/suffix-trees.html Fast String Searching With Suffix Trees] Mark Nelson's tutorial. Has an implementation example written with C++.
	* [http://programmerspatch.blogspot.com.au/2013/02/ukkonens-suffix-tree-algorithm.html Implementation in C with detailed explanation]		* [http://programmerspatch.blogspot.com.au/2013/02/ukkonens-suffix-tree-algorithm.html Implementation in C with detailed explanation]
	* [https://www.cs.cmu.edu/~guyb/realworld/slidesF07/suffix.ppt Lecture slides by Guy Blelloch]		* [https://www.cs.cmu.edu/~guyb/realworld/slidesF07/suffix.ppt Lecture slides by Guy Blelloch]

Pelirodri1248: /* Ukkonen's algorithm example */

2022-06-10T17:01:12Z

Ukkonen's algorithm example

← Previous revision		Revision as of 17:01, 10 June 2022
Line 32:		Line 32:
	# Construct T{{sub\|1}} for S[1] by adding the first character of the string. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|1}} for S[1] by adding the first character of the string. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|2}} for S[1...2] by adding suffixes of xa (xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|2}} for S[1...2] by adding suffixes of xa (xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab (xab,ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab (xab, ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx,abx,bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx, abx, bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa,abxa,bxa,xa and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa, abxa, bxa, xa and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac,abxac,bxac,xac,ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).		# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac, abxac, bxac, xac, ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).

	==References==		==References==

Pelirodri1248: /* Ukkonen's algorithm example */

2022-06-10T17:00:49Z

Ukkonen's algorithm example

← Previous revision		Revision as of 17:00, 10 June 2022
Line 32:		Line 32:
	# Construct T{{sub\|1}} for S[1] by adding the first character of the string. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|1}} for S[1] by adding the first character of the string. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|2}} for S[1...2] by adding suffixes of xa (xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|2}} for S[1...2] by adding suffixes of xa (xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab(xab,ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab (xab,ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx(xabx,abx,bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx,abx,bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa(xabxa,abxa,bxa,xa and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa,abxa,bxa,xa and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac(xabxac,abxac,bxac,xac,ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).		# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac,abxac,bxac,xac,ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).

	==References==		==References==

Pelirodri1248: /* High level description of Ukkonen's algorithm */

2022-06-10T16:59:24Z

High level description of Ukkonen's algorithm

← Previous revision		Revision as of 16:59, 10 June 2022
Line 15:		Line 15:
	Suffix extension is all about adding the next character into the suffix tree built so far. In extension j of phase i+1, algorithm finds the end of S[j...i] (which is already in the tree due to previous phase i) and then it extends S[j...i] to be sure the suffix S[j...i+1] is in the tree. There are three extension rules:		Suffix extension is all about adding the next character into the suffix tree built so far. In extension j of phase i+1, algorithm finds the end of S[j...i] (which is already in the tree due to previous phase i) and then it extends S[j...i] to be sure the suffix S[j...i+1] is in the tree. There are three extension rules:

	# If the path from the root labelled S[j...i] ends at a leaf edge (i.e., S[i] is last character on leaf edge) then character S[i+1] is just added to the end of the label on that leaf edge.		# If the path from the root labelled S[j...i] ends at a leaf edge (i.e., S[i] is last character on leaf edge), then character S[i+1] is just added to the end of the label on that leaf edge.
	# if the path from the root labelled S[j...i] ends at non-leaf edge (i.e., there are more characters after S[i] on path) and next character is not S[i+1], then a new leaf edge with label S[i+1] and number j is created starting from character S[i+1]. A new internal node will also be created if S[1...i] ends inside (in-between) a non-leaf edge.		# if the path from the root labelled S[j...i] ends at a non-leaf edge (i.e., there are more characters after S[i] on path) and next character is not S[i+1], then a new leaf edge with label S[i+1] and number j is created starting from character S[i+1]. A new internal node will also be created if S[1...i] ends inside (in between) a non-leaf edge.
	# If the path from the root labelled S[j..i] ends at non-leaf edge (i.e., there are more characters after S[i] on path) and next character is s[i+1] (already in tree), do nothing.		# If the path from the root labelled S[j..i] ends at a non-leaf edge (i.e., there are more characters after S[i] on path) and next character is S[i+1] (already in tree), do nothing.
	One important point to note is that from a given node (root or internal), there will be one and only one edge starting from one character. There will not be more than one ~~edges~~ going out of any node, starting with same character.		One important point to note is that from a given node (root or internal), there will be one and only one edge starting from one character. There will not be more than one edge going out of any node starting with the same character.

	==Run time==		==Run time==

← Previous revision		Revision as of 18:42, 20 March 2023
Line 34:		Line 34:
	# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab (xab, ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab (xab, ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx, abx, bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx, abx, bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa, abxa, bxa, xa and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa, abxa, bxa, xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac, abxac, bxac, xac, ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).		# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac, abxac, bxac, xac, ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).

← Previous revision		Revision as of 17:01, 10 June 2022
Line 32:		Line 32:
	# Construct T{{sub\|1}} for S[1] by adding the first character of the string. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|1}} for S[1] by adding the first character of the string. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|2}} for S[1...2] by adding suffixes of xa (xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|2}} for S[1...2] by adding suffixes of xa (xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab (xab,ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab (xab, ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx,abx,bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx, abx, bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa,abxa,bxa,xa and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa, abxa, bxa, xa and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac,abxac,bxac,xac,ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).		# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac, abxac, bxac, xac, ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).

	==References==		==References==

← Previous revision		Revision as of 17:00, 10 June 2022
Line 32:		Line 32:
	# Construct T{{sub\|1}} for S[1] by adding the first character of the string. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|1}} for S[1] by adding the first character of the string. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|2}} for S[1...2] by adding suffixes of xa (xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|2}} for S[1...2] by adding suffixes of xa (xa and a). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab(xab,ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.		# Construct T{{sub\|3}} for S[1...3] by adding suffixes of xab (xab,ab and b). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node.
	# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx(xabx,abx,bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Construct T{{sub\|4}} for S[1...4] by adding suffixes of xabx (xabx,abx,bx and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa(xabxa,abxa,bxa,xa and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.		# Constructs T{{sub\|5}} for S[1...5] by adding suffixes of xabxa (xabxa,abxa,bxa,xa and x). Rule 1 applies, which extends the path label in existing leaf edge. Rule 3 applies, do nothing.
	# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac(xabxac,abxac,bxac,xac,ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).		# Constructs T{{sub\|6}} for S[1...6] by adding suffixes of xabxac (xabxac,abxac,bxac,xac,ac and c). Rule 1 applies, which extends the path label in existing leaf edge. Rule 2 applies, which creates a new leaf node (in this case, three new lead edges and two new internal nodes are created).

	==References==		==References==