सबसे लंबे समय तक सामान्य उपसर्ग ऐरे

Question

स्ट्रिंग MISSISSIPPI के लिए Suffix array और LCP array जानकारी निम्न है। मुझे पता है कि LCPstr[i - 1] और str[i] के बीच सबसे लंबे समय तक सामान्य उपसर्ग की लंबाई के बारे में जानकारी देता है। इस स्ट्रिंग के किसी भी दो मनमानी प्रत्यय के बीच मुझे सबसे लंबी सामान्य उपसर्ग लंबाई कैसे मिलती है। उदाहरण के लिए, मैं सबसे लंबे समय तक आम उपसर्ग चाहते MISSISSIPPI और के बीच ISSIPPI

SA LCP 
12 0  $ 
11 0  I$ 
8 1  IPPI$ 
5 1  ISSIPPI$ 
2 4  ISSISSIPPI$ 
1 0  MISSISSIPPI$ 
10 0  PI$ 
9 1  PPI$ 
7 0  SIPPI$ 
4 2  SISSIPPI$ 
6 1  SSIPPI$ 
3 3  SSISSIPPI$ 

Answer 1

http://en.wikipedia.org/wiki/Suffix_array से, हम है कि "तथ्य यह है कि कम से कम LCP मूल्य क्रमबद्ध प्रत्यय के एक लगातार सेट से संबंधित उन सभी के बीच में सबसे लंबे समय तक आम उपसर्ग देता है प्रत्यय भी उपयोगी हो सकता है। " तो आपके मामले में, एमआईएसएसआईएसएसआईपीआई और आईएसएसआईपीपीआई के बीच एलसीपी न्यूनतम (4, 0) = 0.

आप ओ (1) http://en.wikipedia.org/wiki/Range_Minimum_Query के माध्यम से न्यूनतम सीमा में पा सकते हैं, और वहां बहुत सारी जानकारी है वैकल्पिक दृष्टिकोण यदि आप वहां टॉपकोडर लिंक देखते हैं।