प्रोग्राम इंडेक्स को खोजने के लिए जहां एक स्ट्रिंग के सबस्ट्रिंग पूरी तरह से दूसरे स्ट्रिंग के साथ मेल खाते हैं या पाइथन में एक स्थिति में भिन्न होते हैं

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

इसलिए, यदि इनपुट string1 ='tpoint', string2 ='pi' जैसा है, तो आउटपुट 1 2 होगा।

पहली स्ट्रिंग से सबस्ट्रिंग जो दूसरी स्ट्रिंग से मेल खाती है या इंडेक्स 1 और 2 में एक स्थिति में भिन्न होती है, 'पो' और 'ओई' हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें search() । इसमें string1, string2
  . लगेगा
  • str_cat :=string1 + string2
  • z_list :=str_cat के आकार की एक नई सूची 0 के साथ आरंभ की गई
  • z_list[0] :=str_cat का आकार
  • दाएं:=0
  • बाएं:=0
  • i श्रेणी 1 से str_cat के आकार के लिए, करें
    • अगर मैं> सही, तो
      • j :=0
      • जबकि j+i
      • j :=j + 1
    • z_list[i] :=j
    • अगर j> 0, तो
      • बाएं:=मैं
      • दाएं:=i + j-1
  • अन्यथा,
    • k :=i - लेफ्ट
    • r_len :=दाएँ - i + 1
    • अगर z_list[k]
    • z_list[i] :=z_list[k]
  • अन्यथा,
    • एम:=दाएं + 1
    • जबकि m
    • एम :=एम + 1
    • z_list[i] :=m - i
    • बाएं:=मैं
    • दाएं:=एम -1

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

def search(string1, string2):
   str_cat = string1 + string2
   z_list = [0] * len(str_cat)
   z_list[0] = len(str_cat)
   right = 0
   left = 0
   for i in range(1, len(str_cat)):
      if i > right:
         j = 0
         while j + i < len(str_cat) and str_cat[j] == str_cat[j+i]:
            j += 1
         z_list[i] = j
         if j > 0:
            left = i
            right = i + j - 1
      else:
         k = i - left
         r_len = right - i + 1
         if z_list[k] < r_len:
            z_list[i] = z_list[k]
         else:
            m = right + 1
            while m < len(str_cat) and str_cat[m] == str_cat[m -i]:
               m += 1
            z_list[i] = m - i
            left = i
            right = m - 1
      z_list[i] = min(len(string1), z_list[i])
   return z_list[len(string1):]

def solve(str1, str2):
   fwd = search(str2, str1)
   bwrd = search(str2[::-1], str1[::-1])
   bwrd.reverse()
   idx = []
   for i in range(len(str1) - len(str2)+1):
      if fwd[i] + bwrd[i+len(str2)-1] >= len(str2)-1:
         idx.append(str(i))
   if len(idx) == 0:
      return False
   else:
      return (" ".join(idx))

print(solve('tpoint', 'pi'))

इनपुट

'tpoint', 'pi'

आउटपुट

1 2