Suffix Array

Suffix Array কি? 

suffix array হল এমন একটা array যেখানে কোন স্ট্রিং এর সবগুলা suffix string এর index Sorted আকারে থাকবে। আরও সোজা করে বললে, একটা স্ট্রিং এর সাইজ যদি N হয় তাহলে তার N টা suffix string পসিবল। এখন suffix string গুলাকে যদি lexicographical ভাবে সর্ট করি তাহলে suffix starting এর যে index গুলা array আকারে পাব তাকেই suffix array বলা হচ্ছে। যেমন একটাস্ট্রিংঃ mississippi এর সবগুলা suffix string হলঃ