python - पायथन स्ट्रिंग 'में' ऑपरेटर कार्यान्वयन एल्गोरिथ्म और समय जटिलता



string algorithm (1)

यह बोयर-मूर और हॉर्सपुल का संयोजन है

आप यहां सी कोड देख सकते हैं :

बोअर-मूर और हॉर्सपुल के बीच के मिश्रण के आधार पर तेजी से खोज / गिनती कार्यान्वयन, शीर्ष पर कुछ और घंटी और सीटी के साथ। कुछ और पृष्ठभूमि के लिए, देखें: http://effbot.org/zone/stringlib.htm

ऊपर दिए गए लिंक से:

नए एल्गोरिदम को डिजाइन करते समय, मैं निम्नलिखित बाधाओं का इस्तेमाल करता था:

  • सभी परीक्षण के मामलों (वास्तविक जीवन कोड पर आधारित) के लिए वर्तमान ब्रूट-बल एल्गोरिथ्म की तुलना में तेज़ होना चाहिए, जिम ह्यूगुनिन का खराब-केस परीक्षण सहित
  • छोटे सेटअप ओवरहेड; तेज गति में गतिशील आवंटन (ओ (एम) की गति के लिए, हे (1) भंडारण के लिए)
  • अच्छे मामलों में उपलाइन खोज व्यवहार (हे (एन / एम))
  • सबसे खराब मामले में मौजूदा एल्गोरिदम से भी बदतर नहीं (हे (एनएम))
  • दोनों 8-बिट स्ट्रिंग्स और 16-बिट या 32-बिट यूनिकोड स्ट्रिंग्स के लिए अच्छी तरह से काम करना चाहिए (कोई ओ (σ) निर्भरता नहीं)
  • कई वास्तविक जीवन की खोज अच्छी जानी चाहिए, बहुत कम मामलों को काफी सरल क्रियान्वयन होना चाहिए

मैं सोच रहा हूँ कि कैसे ऑपरेटर में लागू होता है, उदाहरण के लिए

>>> s1 = 'abcdef'
>>> s2 = 'bcd'
>>> s2 in s1
True

CPython में, जो एल्गोरिथ्म का प्रयोग स्ट्रिंग मैच को लागू करने के लिए किया जाता है, और समय की जटिलता क्या है? क्या इस बारे में कोई आधिकारिक दस्तावेज या विकी है?





cpython