Suffix Array is a sorted array of all suffixes of a string T with usually long length n. It is a simple, yet powerful data structure which is used, among others, in full text indices, data compression algorithms, and within the field of bioinformatics. This data structure is very related to Suffix Tree data structure.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
All available operations on the Sufix Array are listed below.
- Construct Suffix Array (SA) is the O(n log n) Suffix Array construction algorithm based on the idea by Karp, Miller, & Rosenberg (1972) that sort prefixes of the suffix in increasing length (1, 2, 4, 8, ...).
- Search utilizes the fact that the suffixes in Suffix Array are sorted and call two binary searches in O(m log n) to find the first and the last occurrence(s) of pattern string P of length m.
- Longest Common Prefix (LCP) between two adjacent suffixes (excluding the first suffix) can be computed in O(n) using the Permuted LCP (PLCP) theorem.
- Longest Repeated Substring (LRS) is a simple O(n) algorithm that finds the suffix with the highest LCP value.
- Longest Common Substring (LCS) is a simple O(n) algorithm that finds the suffix with the highest LCP value that comes from two different strings.
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
You are allowed to use/modify our implementation code for fast Suffix Array+LCP:
sa_lcp.cpp
sa_lcp.java
sa_lcp.py
sa_lcp.ml
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
构造后缀数组
搜索
最长公共前缀
最长重复子串
最长公共子串