Suffix Array
সাফিক্স অ্যারে
String-এর সব suffix lexicographic order-এ সাজিয়ে তাদের start index-এর array — binary search দিয়ে substring খোঁজা O(m log n)।
also: suffix table, suffix sorting
banana-র suffix array:
sorted suffixes: a ana anana banana na nana
SA = [5, 1, 3, 0, 4, 2]Substring খোঁজা মানে suffix-এর prefix খোঁজা — sorted list-এ binary search খাটে, তাই O(m log n)।
Trie-এর প্রশ্নগুলোর উত্তর দেয়, কিন্তু memory মাত্র n integer — genome-scale text-এ এই পার্থক্যই সব। LCP array (পরপর দুই suffix-এর common prefix length) জুড়লে longest repeated substring, occurrence count — সব প্রায় linear। Bioinformatics আর full-text search-এর নির্ভরযোগ্য অস্ত্র।