प्रत्यय पेड़ों के लिए Ukkonen के एल्गोरिदम को समझना

Question

मैं प्रत्यय पेड़ों के निर्माण के लिए Ukkonen के एल्गोरिदम के साथ कुछ काम कर रहा हूं, लेकिन मैं इसकी रैखिक-समय जटिलता के लिए लेखक के स्पष्टीकरण के कुछ हिस्सों को समझ नहीं रहा हूं।

मैंने एल्गोरिदम सीखा है और इसे कोड किया है, लेकिन जिस पेपर का मैं मुख्य स्रोत (लिंक बोले) के रूप में उपयोग कर रहा हूं, कुछ हिस्सों में थोड़ी उलझन में है, इसलिए यह वास्तव में मेरे लिए स्पष्ट नहीं है कि एल्गोरिदम रैखिक क्यों है ।

कोई मदद? धन्यवाद। Ukkonen के कागज के लिए

लिंक: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Answer 1

Gusfield के string algorithms textbook की एक प्रति का पता लगाएं। यह मैंने देखा है प्रत्यय पेड़ निर्माण का सबसे अच्छा प्रदर्शन मिला है। रैखिकता उच्च स्तरीय एल्गोरिदम के कई अनुकूलन का एक आश्चर्यजनक परिणाम है।