एलआरएस सरणी

Question

के साथ बढ़ाए गए कारक ऑरैकल का उपयोग करके एकाधिक स्ट्रिंग्स का सबसे लंबा सामान्य सबस्ट्रिंग पाएं। क्या हम कई स्ट्रिंग्स के सबसे लंबे सामान्य सबस्ट्रिंग की गणना करने के लिए प्रत्यय लिंक (paper here) के साथ एक कारक-ऑरैकल का उपयोग कर सकते हैं? यहां, सबस्ट्रिंग मूल स्ट्रिंग का कोई भी हिस्सा है। उदाहरण के लिए "एबीसी" "ffabcgg" का सबस्ट्रिंग है, जबकि "abg" नहीं है।

मुझे दो स्ट्रिंग्स s1 और s2 की अधिकतम लंबाई सामान्य सबस्ट्रिंग की गणना करने का एक तरीका मिला है। यह दो तारों को एक चरित्र का उपयोग करके काम करता है, उदाहरण में उदाहरण के लिए '$'। फिर लंबाई के साथ s के प्रत्येक उपसर्ग के लिए, हम इसकी एलआरएस (सबसे लंबी बार-बार प्रत्यय) लंबाई lrs[i] और sp[i] (इसके एलआरएस के पहले अवसर की अंतिम स्थिति) की गणना करते हैं। अंत में, इस सवाल का जवाब

max{lrs[i]| i >= |s1| + 2 and sp[i] <= |s1|} 

मैं एक सी ++ प्रोग्राम इस विधि है, जो अपने लैपटॉप जब |s1|+|s2| <= 200000 पर 200 मि.से भीतर समस्या का समाधान कर सकते हैं, कारक ओरेकल का उपयोग कर का उपयोग करता है लिखा है है।

s1 = 'ffabcgg' 
s2 = 'gfbcge' 
s = s1+'$'+s2 
    = 'ffabcgg$gfbcge' 
p: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 
s: f f a b c g g $ g f b c g e 
sp: 0 1 0 0 0 0 6 0 6 1 4 5 6 0 
lrs:0 1 0 0 0 0 1 0 1 1 1 2 3 0 

ans = lrs[13] = 3 

मैं दोनों समस्याओं उच्च दक्षता के साथ प्रत्यय सरणी और प्रत्यय-वृक्ष का उपयोग कर हल किया जा सकता है, लेकिन मुझे आश्चर्य है कि अगर वहाँ एक विधि कारक ओरेकल का उपयोग कर इसे हल करने के लिए है। मुझे इसमें दिलचस्पी है क्योंकि कारक ऑरैकल बनाना आसान है (सी ++ की 30 लाइनों के साथ, प्रत्यय-सरणी के बारे में 60 की जरूरत है, और प्रत्यय-पेड़ की जरूरत 150 है), और यह प्रत्यय-सरणी और प्रत्यय-पेड़ की तुलना में तेज़ी से चलती है।

आप this OnlineJudge में पहली समस्या की अपनी विधि का परीक्षण कर सकते हैं, और here में दूसरी समस्या का परीक्षण कर सकते हैं।

Answer 1

हम गणना करने के लिए कई तार के सबसे लंबे समय तक आम-स्ट्रिंग प्रत्यय लिंक (कागज यहाँ) के साथ एक कारक-ओरेकल का उपयोग कर सकते हैं?

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

# combine with unique joiners 
>>> s = "abcdefg" + "1" + "hijcdekl" + "2" + "mncdop" 
>>> factor_oracle(s) 
"cd" 

अपनी रेखीय-समय और स्थान एल्गोरिथ्म के भाग के रूप में कारक-ओरेकल जल्दी के रूप में इनपुट तार के बीच ब्रेक अंक rediscover:

को देखते हुए abcdefg और hijcdekl और mncdop, सबसे लंबे समय तक आम-स्ट्रिंग cd लगता है आम कारकों के लिए अपनी खोज का हिस्सा (अद्वितीय योजक अब तक उपलब्ध सर्वोत्तम कारक को विस्तारित करने के लिए प्रदान करते हैं और तत्काल क्यू) प्रदान करते हैं।