पायथन में अलग-अलग अनुक्रमों की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक स्ट्रिंग s है, हमें स्ट्रिंग s के अलग-अलग अनुक्रमों की संख्या गिननी है। अगर उत्तर बहुत बड़ा है तो परिणाम मॉड्यूलो 10^9 + 7 लौटाएं।

इसलिए, यदि इनपुट s ="bab" जैसा है, तो आउटपुट 6 होगा क्योंकि 6 अलग-अलग क्रम हैं, ये "a", "b, "ba", "ab", "bb", "abb" हैं। ।

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

• dp:=एक सरणी जिसका आकार s के समान है और 0 से भरा है

• मी :=10^9 + 7

• प्रत्येक अनुक्रमणिका i और s में आइटम चार के लिए, करें

  • ind :=दायीं ओर से s में i-th char की अनुक्रमणिका

  • डीपी [i]:=1 + (डीपी में सभी तत्वों का योग [इंडेक्स 0 से i-1 तक]) मॉड एम अगर इंड -1 के समान है अन्यथा (डीपी में सभी तत्वों का योग [इंडेक्स इंड से i-1 तक) ]) मॉड एम

• dp mod m में सभी तत्वों का रिटर्न योग

उदाहरण

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

def solve(s):
   dp, m = [0] * len(s), 10**9 + 7
   for i, char in enumerate(s):
      ind = s.rfind(char, 0, i)
      dp[i] = 1 + sum(dp[:i]) % m if ind == -1 else sum(dp[ind:i]) % m
   return sum(dp) % m

s = "bab"
print(solve(s))

इनपुट

"abcd", "abcdbcd"

आउटपुट

6