পাইথনের একটি স্ট্রিংয়ে প্যালিনড্রোমিক সীমানা খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং str প্রদান করা হয়েছে। একটি স্ট্রিং এর বর্ডার হল একটি সাবস্ট্রিং যা একটি সঠিক উপসর্গ এবং সেই স্ট্রিং এর একটি প্রত্যয়। উদাহরণস্বরূপ, 'আব' হল 'অবাব' স্ট্রিংয়ের একটি সীমানা। বর্ডার স্ট্রিং যদি প্যালিনড্রোম হয় তবে একটি সীমানাকে প্যালিনড্রোম বর্ডার বলা হয়। এখন ধরুন প্রদত্ত স্ট্রিং str এ প্যালিনড্রোম সীমানার f(str) সংখ্যা রয়েছে। আমাদের str_k-এর সমস্ত অ-খালি সাবস্ট্রিংগুলির জন্য f(str_k) এর যোগফল বের করতে হবে। যোগফল বড় হতে পারে, তাই একটি মডুলো অপারেশন 10^9 + 7 দ্বারা সঞ্চালিত হতে পারে।

সুতরাং, যদি ইনপুট str ='pqpqp' এর মত হয়, তাহলে আউটপুট হবে 5এখানে 'pqpqp' স্ট্রিংটির 15টি সাবস্ট্রিং আছে; তবে মাত্র 4টি সাবস্ট্রিংয়ের প্যালিনড্রোমিক সীমানা রয়েছে। স্ট্রিংগুলি হল:

pqp : f(pqp) = 1
pqpqp : f(pqpqp) = 2
qpq : f(qpq) = 1
pqp : f(pqp) = 1

The sum of these values are 1 + 2 + 1 + 1 = 5.

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

একটি ফাংশন palindrome_calculator() সংজ্ঞায়িত করুন। এটি input_dict
- উত্তর :=0
- প্রতিটি আইটেম 1, আইটেম 2 এর জন্য input_dict এর মানগুলিতে করুন
  - উত্তর :=উত্তর + আইটেম 2 *((আইটেম 2 - 1) / 2 এর ফ্লোর মান)
- উত্তর ফেরত দিন
একটি ফাংশন str_check() সংজ্ঞায়িত করুন। এটি স্ট্রিং
- t_str :=স্ট্রিং[0]
- স্ট্রিং-এর প্রতিটি s-এর জন্য, করুন
  - যদি s t_str এর মত না হয়, তাহলে
    - মিথ্যে ফেরত দিন
  - সত্য ফেরান
একটি ফাংশন string_res() সংজ্ঞায়িত করুন। এটি স্ট্রিং
- উত্তর :=0
- আমি রেঞ্জ 2 থেকে স্ট্রিং + 1 এর আকারের জন্য,
  - উত্তর :=ans + i *((i - 1) / 2 এর ফ্লোর মান)
  - উত্তর :=উত্তর মোড 1000000007
- প্রত্যাবর্তন এবং
যদি str_check(string) True হয়, তাহলে
- রিটার্ন স্ট্রিং_রেস(স্ট্রিং)
উত্তর :=0
odd_list :=একটি নতুন তালিকা যাতে একটি নতুন তালিকা, একটি নতুন মানচিত্র এবং 1
স্ট্রিং-এর প্রতিটি s-এর জন্য, করুন
- যদি s odd_list[1]-এ উপস্থিত না থাকে, তাহলে
  - বিজোড়_তালিকা[1, s] :=0
- বিজোড়_তালিকা[1, s] :=odd_list[1, s] + 1
আমি 0 থেকে স্ট্রিং এর আকারের মধ্যে,
- odd_list[0] এর শেষে i ঢোকান
উত্তর :=ans + palindrome_calculator(odd_list[1])
even_list :=একটি নতুন তালিকা যাতে একটি নতুন তালিকা, একটি নতুন মানচিত্র এবং 1
আমি 0 থেকে স্ট্রিং এর আকার - 1 এর মধ্যে, কর
- যদি স্ট্রিং[i] স্ট্রিং[i + 1] এর মতো হয়, তাহলে
  - even_list[0] এর শেষে i ঢোকান
  - tmp :=স্ট্রিং[সূচী i থেকে i + 2]
  - যদি tmp ইভেন_লিস্টে উপস্থিত না থাকে[1], তাহলে
    - even_list[1, tmp] :=0
  - even_list[1, tmp] :=even_list[1, tmp] + 1
উত্তর :=ans + palindrome_calculator(even_list[1])
পরিসীমা 3 থেকে স্ট্রিংয়ের আকারের ভ্যালের জন্য, করুন
- যদি val mod 2 0 এর মত হয়, তাহলে
  - wt :=even_list
- অন্যথায়,
  - wt :=odd_list
- new_t :=একটি নতুন তালিকা যেখানে একটি নতুন তালিকা, একটি নতুন মানচিত্র এবং ভ্যাল রয়েছে
- wt[0]-এ প্রতিটি সূচকের জন্য, করুন
  - যদি index - 1>=0 এবং index + val - 2 <স্ট্রিং এবং স্ট্রিং এর আকার [index - 1] স্ট্রিং[index + val - 2] এর মত হয়, তাহলে
    - insert index - 1 new_t[0] এর শেষে
    - tmp :=স্ট্রিং[সূচী সূচক - 1 থেকে সূচক - 1 + ভ্যাল]
    - যদি tmp new_t[1]-এ উপস্থিত না থাকে, তাহলে
      - new_t[1, tmp] :=0
    - new_t[1, tmp] :=new_t[1, tmp] + 1
- উত্তর :=ans + palindrome_calculator(new_t[1])
- উত্তর :=উত্তর মোড 1000000007
- যদি val mod 2 0 এর মত হয়, তাহলে
  - even_list :=new_t
- অন্যথায়,
  - বিজোড়_তালিকা :=নতুন_টি
উত্তর ফেরত দিন

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

def palindrome_calculator(input_dict):

   ans = 0
   for item1, item2 in input_dict.items():
      ans += item2 * (item2 - 1) // 2
   return ans

def str_check(string):
   t_str = string[0]
   for s in string:
      if s != t_str:
         return False
   return True

def string_res(string):
   ans = 0
   for i in range(2, len(string) + 1):
      ans += i * (i - 1) // 2
      ans %= 1000000007
   return ans

def solve(string):
   if str_check(string):
      return string_res(string)
   ans = 0
   odd_list = [[], {}, 1]
   for s in string:
      if s not in odd_list[1]:
         odd_list[1][s] = 0
      odd_list[1][s] += 1
   for i in range(len(string)):
      odd_list[0].append(i)
   ans += palindrome_calculator(odd_list[1])
   even_list = [[], {}, 1]
   for i in range(len(string) - 1):
      if string[i] == string[i + 1]:
         even_list[0].append(i)
         tmp = string[i:i + 2]
         if tmp not in even_list[1]:
            even_list[1][tmp] = 0
         even_list[1][tmp] += 1
   ans += palindrome_calculator(even_list[1])
   for val in range(3, len(string)):
      if val % 2 == 0:
         wt = even_list
      else:
         wt = odd_list
      new_t = [[], {}, val]
      for index in wt[0]:
         if index - 1 >= 0 and index + val - 2 < len(string) and string[index - 1] == string[index + val - 2]:
            new_t[0].append(index - 1)
            tmp = string[index - 1 : index - 1 + val]
            if tmp not in new_t[1]:
               new_t[1][tmp] = 0
            new_t[1][tmp] += 1
      ans += palindrome_calculator(new_t[1])
      ans %= 1000000007
      if val % 2 == 0:
         even_list = new_t
      else:
         odd_list = new_t
   return ans

print(solve('pqpqp'))

ইনপুট

'pqpqp'