दिए गए स्ट्रिंग एस, सबसे छोटी स्ट्रिंग टी खोजें, जैसे कि, टी^एम = एस

Question

दिए गए स्ट्रिंग एस, सबसे छोटी स्ट्रिंग टी, जैसे कि टी^एम = एस खोजें।

उदाहरण:

s="aabbb" => t="aabbb" 
s="abab" => t = "ab" 

कितनी तेजी से यह किया जा सकता है?

बेशक नैतिक रूप से, हर एम विभाजन के लिए |, मैं कोशिश कर सकता हूं अगर सबस्ट्रिंग (एस, 0, | एस |/एम)^एम = एस।

कोई ओ (डी (| एस |) एन) समय में समाधान का पता लगा सकता है, जहां डी (एक्स) एस के divisors की संख्या है। क्या इसे और अधिक कुशलतापूर्वक किया जा सकता है?

Answer 1

यह एक स्ट्रिंग की अवधि की गणना करने की समस्या है। Knuth, Morris and Pratt's sequential string matching algorithm शुरू करने के लिए एक अच्छी जगह है। यह 1 9 77 से "स्ट्रिंग पैटर्न मिलानिंग स्ट्रिंग्स" नामक एक पेपर में है।

यदि आप इसके साथ फैंसी प्राप्त करना चाहते हैं, तो ब्रेस्लॉयर द्वारा "समांतर में एक स्ट्रिंग के सभी अवधि और प्रारंभिक पालिंड्रोम ढूंढना" पेपर देखें और 1991 उनके सार से में Galil:

एक इष्टतम हे (लॉग लॉग ऑन एन) एक स्ट्रिंग के सभी अवधि की गणना प्रस्तुत किया जाता है के लिए समय CRCW-बच्चों की गाड़ी एल्गोरिथ्म। पिछला समांतर एल्गोरिदम गणना केवल तभी करें जब यह स्ट्रिंग की लंबाई के आधे से कम हो। इस एल्गोरिदम का उपयोग के सभी प्रारंभिक palindromes को एक ही समय और प्रोसेसर सीमाओं में एक स्ट्रिंग को खोजने के लिए किया जा सकता है। दोनों एल्गोरिदम सामान्य वर्णमाला पर सबसे तेज़ संभव हैं। स्ट्रिंग [3] की अवधि खोजने के लिए पहले ज्ञात निचले बाध्यता के संशोधन द्वारा पैलिंड्रोम ढूंढने के लिए हम कम बाध्य प्राप्त करते हैं। जब पी प्रोसेसर उपलब्ध हैं तो सीमाएं \ Theta (डी एन पी ई + लॉग लॉग डी 1 + पी = एन 2 पी) बन जाती हैं।

Answer 2

बोयर-मूर के एक संशोधन संभवतः हे (एन) में इस संभाल सकता जहां n रों

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

Answer 3

हाँ आप O(|s|) समय में कर सकते हैं की लंबाई है।

आप O(n+m) समय में m की "स्रोत" स्ट्रिंग में n की "लक्ष्य" स्ट्रिंग की खोज कर सकते हैं। उस पर आधारित एक समाधान बनाएँ।

दोनों स्रोत और लक्ष्य s होने दें। एक अतिरिक्त बाधा यह है कि 1 और स्रोत में कोई भी स्थिति जो |s| को विभाजित नहीं करती है, मैच के लिए मान्य प्रारंभिक स्थिति नहीं है। बेशक खोज प्रति से हमेशा असफल हो जाएगी। लेकिन यदि कोई आंशिक मिलान है और आप सोर्स स्ट्रिंग के अंत तक पहुंच गए हैं, तो आपके पास मूल समस्या का समाधान है।

Answer 4

मैं वास्तव में इस बात z-कलन विधि कहा जाता है की तरह: http://www.utdallas.edu/~besp/demo/John2010/z-algorithm.htm

हर स्थिति के लिए यह सबसे लंबे समय तक सबस्ट्रिंग वहाँ से शुरू की गणना करता है, वह भी पूरी स्ट्रिंग का एक उपसर्ग है। (पाठ्यक्रम के रैखिक समय में)।

a a b c a a b x a a a z 
    1 0 0 3 1 0 0 2 2 1 0 

इस "Z-तालिका" को देखते हुए यह सभी स्ट्रिंग पूरी बात करने के लिए exponentiated किया जा सकता है खोजने के लिए आसान है। pos+z[pos] = n पर बस सभी पदों की जांच करें।

हमारे मामले में:

a b a b 
    0 2 0 

यहाँ pos = 2 आप देता है 2+z[2] = 4 = n इसलिए कम से कम स्ट्रिंग आप उपयोग कर सकते लंबाई 2.

यह भी आप मामलों को खोजने के लिए अनुमति देगा में से एक है, जहां केवल एक उपसर्ग exponentiated स्ट्रिंग मैचों की तरह की:

a b c a 
    0 0 1 

यहाँ (abc)^2 अपने मूल करने के लिए नीचे काटा जा सकता है स्ट्रिंग। लेकिन निश्चित रूप से, यदि आप इस तरह के मैचों नहीं चाहते हैं, तो केवल divisors पर जाएं।