Advanced Data Structures | Suffix Array [01] Introduction | شرح بالعربي
Suffix Array
Introduction
Examples
Space Complexity
Search Complexity
==============================
Download Materials :
https://github.com/Abdalla2030/Educat...
==============================
A suffix array will contain integers that represent the starting indexes of the all the suffixes of a given string, after the aforementioned suffixes are sorted.
A suffix array is a sorted array of all suffixes of a given string. is similar to Suffix Tree which is compressed trie of all suffixes of the given text.
A suffix array can be constructed from Suffix tree by doing a DFS traversal of the suffix tree. In fact Suffix array and suffix tree both can be constructed from each other in linear time.
Advantages of suffix arrays over suffix trees include improved space requirements, simpler linear time construction algorithms (e.g., compared to Ukkonen’s algorithm) and improved cache locality