Longest repeated substring problem
कंप्यूटर विज्ञान में, सबसे लंबी बार-बार दोहराई जाने वाली सबस्ट्रिंग समस्या एक स्ट्रिंग की सबसे लंबी सबस्ट्रिंग खोजने की समस्या है जो कम से कम दो बार होती है। इस समस्या को रैखिक समय और स्थान में स्ट्रिंग के लिए एक प्रत्यय ट्री ('$' जैसे एक विशेष एंड-ऑफ-स्ट्रिंग प्रतीक के साथ) बनाकर और एक से अधिक बच्चों के साथ ट्री में सबसे गहरे आंतरिक नोड को ढूंढकर हल किया जा सकता है। गहराई को मूल से पार किए गए वर्णों की संख्या से मापा जाता है। जड़ से इस तरह के नोड तक किनारों द्वारा वर्तनी स्ट्रिंग एक सबसे लंबी दोहराए गए सबस्ट्रिंग है। कम से कम घटनाओं के साथ सबसे लंबे सबस्ट्रिंग को खोजने की समस्या को पहले प्रत्येक आंतरिक नोड के लिए पत्ती के वंशजों की संख्या की गणना करने के लिए पेड़ को पूर्व-संसाधित करके और फिर कम से कम पत्ती के वंशजों के साथ सबसे गहरे नोड को ढूंढकर हल किया जा सकता है। ओवरलैपिंग रिपीट्स से बचने के लिए, आप देख सकते हैं कि प्रत्यय लंबाई की सूची में उपसर्ग-लंबाई के अंतर से कम के साथ कोई लगातार तत्व नहीं है। स्ट्रिंग "एटीसीजीएटीसीजीए $" के साथ आकृति में, सबसे लंबी सबस्ट्रिंग जो कम से कम दो बार दोहराती है वह "एटीसीजीए" है। बाहरी लिंक सी सफिक्स ट्री ऑनलाइन डेमो का उपयोग करके सबसे लंबे बार-बार दोहराये जाने वाले उप-तार का कार्यान्वयनः तारों पर सबसे लंबे बार-बार दोहराये जाने वाले उप-तार की समस्याएं औपचारिक भाषा संयोजन