पायथन में समरूप सबस्ट्रिंग की संख्या गिनने का कार्यक्रम

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

इसलिए, यदि इनपुट s ="xyyzzxx" जैसा है, तो आउटपुट 13 होगा क्योंकि समरूप सबस्ट्रिंग की तरह सूचीबद्ध हैं

1."x" तीन बार दिखाई देता है।
"xx" एक बार दिखाई देता है।
3. "y" दो बार प्रकट होता है।
"yy" एक बार दिखाई देता है।
5. "z" तीन बार दिखाई देता है।
"zz" दो बार प्रकट होता है।
"zzz" एक बार दिखाई देता है।

तो , (3 + 1 + 2 + 1 + 3 + 2 + 1) =13.

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

s :=s "@" को जोड़ना
h:=एक नया नक्शा
पिछला:=एस[0]
सी:=1
इंडेक्स 1 से अंत तक प्रत्येक i के लिए, करें
- अगर पिछला मैं जैसा नहीं है, तो
  - अगर पिछला*c h में मौजूद है, तो
    - एच[पिछला*सी] :=एच[पिछला*सी] + 1
  - अन्यथा,
    - ज[पिछला*सी]:=1
  - सी:=1
- अगर पिछला मैं जैसा ही है, तो
  - सी:=सी + 1
- पिछला:=मैं
फिन:=0
प्रत्येक के लिए i in h, do
- t:=मैं का आकार
- कश्मीर:=0
- जबकि t 0 के समान नहीं है, करें
  - कश्मीर:=के + टी
  - टी:=टी - 1
- फिन:=फिन + के*एच[i]
रिटर्न फिन मॉड 10^9+7

उदाहरण

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

def solve(s):
   s+="@"
   h={}
   prev=s[0]
   c=1
   for i in s[1:]:
      if prev!=i:
         if prev*c in h:
            h[prev*c]+=1
         else:
            h[prev*c]=1
         c=1
      if prev == i:
         c += 1
      prev = i
   fin=0
   for i in h:
      t=len(i)
      k=0
      while t!=0:
         k+=t
         t-=1
      fin+=k*h[i]
   return fin % 1000000007

s = "xyyzzzxx"
print(solve(s))

इनपुट

"xyyzzzxx"