McCrieght’s algorithm for linear-time suffix tree construction
McCrieght’s algorithm for linear-time suffix tree construction
Copyright By PowCoder代写 加微信 powcoder
Example string: AAAAAAA
1 2 3 4 5 6 7 8
A A A A A A A $
Conventions:
Ti corresponds to the tree after i iterations.
Suffix numbering and string indexing starts from 1 and ends at n.
Only for convenience in presentation, edge-labels are shown as strings.
In the implementation, it is assumed that edge-labels are stored
as a pair of integers.
Initial tree:
Denotes suffix links
Example string: AAAAAAA
1 2 3 4 5 6 7 8
A A A A A A A $
Tally of cost
Number of character comparisons 0
Number of node hops 0
Iteration: 1
For this iteration:
Example string: AAAAAAA
1 2 3 4 5 6 7 8
A A A A A A A $
Tally of cost
Number of character comparisons 7
Number of node hops 0
Iteration: 2
For this iteration:
Example string: AAAAAAA
1 2 3 4 5 6 7 8
A A A A A A A $
Tally of cost
Number of character comparisons 1
Number of node hops 1
Iteration: 3
For this iteration:
Example string: AAAAAAA
1 2 3 4 5 6 7 8
A A A A A A A $
Tally of cost
Number of character comparisons 1
Number of node hops 1
Iteration: 4
For this iteration:
Example string: AAAAAAA
1 2 3 4 5 6 7 8
A A A A A A A $
Tally of cost
Number of character comparisons 1
Number of node hops 1
Iteration: 5
For this iteration:
Example string: AAAAAAA
1 2 3 4 5 6 7 8
A A A A A A A $
Tally of cost
Number of character comparisons 1
Number of node hops 1
Iteration: 6
For this iteration:
Example string: AAAAAAA
1 2 3 4 5 6 7 8
A A A A A A A $
Tally of cost
Number of character comparisons 1
Number of node hops 1
Iteration: 7
For this iteration:
Example string: AAAAAAA
1 2 3 4 5 6 7 8
A A A A A A A $
Tally of cost
Number of character comparisons 0
Number of node hops 0
Iteration: 8
TOTAL Tally of cost over all iterations
Number of character comparisons 12
Number of node hops 5
For this iteration:
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com