পাইথনে সমজাতীয় সাবস্ট্রিংয়ের সংখ্যা গণনা করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের s এর সমজাতীয় সাবস্ট্রিংগুলির সংখ্যা বের করতে হবে। উত্তরটি অনেক বড় হতে পারে, তাই উত্তর মডিউল 10^9+7 ফেরত দিন। একটি স্ট্রিংকে সমজাতীয় বলা হয় যখন স্ট্রিংয়ের সমস্ত অক্ষর একই হয়৷

সুতরাং, যদি ইনপুটটি s ="xyyzzzxx" এর মতো হয়, তাহলে আউটপুট হবে 13 কারণ সমজাতীয় সাবস্ট্রিংগুলি যেমন তালিকাভুক্ত করা হয়েছে

1."x" তিনবার প্রদর্শিত হয়৷
৷
"xx" একবার প্রদর্শিত হয়৷
3. "y" দুবার প্রদর্শিত হয়৷
৷
"yy" একবার প্রদর্শিত হয়৷
5. "z" তিনবার প্রদর্শিত হয়৷
৷
"zz" দুবার প্রদর্শিত হয়৷
৷
"zzz" একবার প্রদর্শিত হয়৷

তাই, (3 + 1 + 2 + 1 + 3 + 2 + 1) =13।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

s :=s concatenate "@"
h:=একটি নতুন মানচিত্র
পূর্ববর্তী:=s[0]
c:=1
সূচী 1 থেকে শেষ পর্যন্ত প্রতিটি i-এর জন্য, করুন
- যদি পূর্ববর্তী i এর মত না হয়, তাহলে
  - যদি পূর্ববর্তী*c h তে উপস্থিত থাকে, তাহলে
    - h[prev*c] :=h[prev*c] + 1
  - অন্যথায়,
    - h[prev*c]:=1
  - c:=1
- যদি পূর্ববর্তী i এর মত হয়, তাহলে
  - c :=c + 1
- পূর্ববর্তী :=i
ফিন:=0
প্রতিটি i এর জন্য h, do
- t:=i
  এর আকার
- k:=0
- যদিও t 0 এর মত নয়, করুন
  - k :=k + t
  - t :=t - 1
- fin :=fin + k*h[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"