पायथन में एक स्ट्रिंग और उसके सबस्ट्रिंग की कुल समानता खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक स्ट्रिंग s है। हमें प्रत्येक प्रत्यय के साथ स्ट्रिंग s की समानता का योग ज्ञात करना है। यहां दो स्ट्रिंग्स के बीच समानता दोनों स्ट्रिंग्स के लिए सामान्य सबसे लंबे उपसर्ग की लंबाई है।

इसलिए, यदि इनपुट s ="pqpqpp" जैसा है, तो आउटपुट 11 होगा क्योंकि स्ट्रिंग के प्रत्यय "pqpqpp", "qpqpp", "pqpp", "qpp", "pp" और "p" हैं। स्ट्रिंग "pqpqpp" के साथ इन सबस्ट्रिंग्स की समानताएं 6,0,3,0,1 और 1 हैं। तो योग 6 + 0 + 3 + 0 + 1 + 1 =11 है।

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

• लंबाई:=s का आकार
• कुल :=लंबाई
• z :=एक सूची जिसमें प्रारंभ में 0 है
• एल:=0, आर:=0
• k के लिए 1 से लंबाई -1 तक के लिए, करें
  • अगर के> आर, तो
    • मैच:=0
    • सूचकांक :=k
  • सूचकांक <लंबाई के दौरान, करते हैं
    • यदि s[index], s[match] के समान है, तो
      • मैच :=मैच + 1
      • सूचकांक :=अनुक्रमणिका + 1
    • अन्यथा,
      • लूप से बाहर आएं
  • z के अंत में मैच डालें
  • अगर मैच> 0, तो
    • कुल :=कुल + मैच
    • l :=k
    • r :=अनुक्रमणिका-1
  • अन्यथा,
    • अगर z[k-l] <(r-k)+1, तो
      • z के अंत में z[k-l] डालें
      • कुल:=कुल + z[k-l]
    • अन्यथा,
      • मैच:=आर-के
      • सूचकांक :=r
      • सूचकांक <लंबाई के दौरान, करते हैं
        • यदि s[index], s[match] के समान है, तो
          • मैच :=मैच + 1
          • सूचकांक :=अनुक्रमणिका + 1
        • अन्यथा,
          • लूप से बाहर आएं
      • z के अंत में मैच डालें
      • कुल :=कुल + मैच
      • l :=k
      • r :=अनुक्रमणिका-1
• कुल वापसी

उदाहरण

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

def solve(s):
   length = len(s)
   total = length

   z = [0]
   l = 0
   r = 0

   for k in range(1,length):
      if k > r:
         match=0
         index = k
         while index < length:
            if s[index] == s[match]:
               match +=1
               index +=1
            else:
               break
         z.append(match)
         if match > 0:
            total+=match
            l = k
            r = index-1
      else:
         if z[k-l] < (r-k)+1:
            z.append(z[k-l])
            total+=z[k-l]
         else:
            match = r-k
            index = r
            while index < length:
               if s[index] == s[match]:
                  match +=1
                  index +=1
               else:
                  break
            z.append(match)
            total+=match
            l = k
            r = index-1
   return total

s = "pqpqpp"
print(solve(s))

इनपुट

"pqpqpp"

आउटपुट

11