पायथन में एक स्ट्रिंग में पैलिंड्रोमिक सीमाओं का पता लगाने का कार्यक्रम

मान लीजिए कि हमें एक स्ट्रिंग स्ट्र प्रदान की जाती है। एक स्ट्रिंग की एक सीमा एक सबस्ट्रिंग है जो एक उचित उपसर्ग और उस स्ट्रिंग का प्रत्यय है। उदाहरण के लिए, 'अब' स्ट्रिंग 'अबाबाब' की सीमा है। यदि बॉर्डर स्ट्रिंग पैलिंड्रोम है तो बॉर्डर को पैलिंड्रोम बॉर्डर कहा जाता है। अब मान लीजिए कि दिए गए स्ट्रिंग str में f(str) पैलिंड्रोम बॉर्डर की संख्या है। हमें 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 करें
    • Ans :=ans + item2 *(floor value of (item2 - 1)/2)
  • वापसी उत्तर
• एक फ़ंक्शन परिभाषित करें str_check() । यह स्ट्रिंग लेगा
  • t_str :=string[0]
  • स्ट्रिंग में प्रत्येक s के लिए, करें
    • यदि s t_str के समान नहीं है, तो
      • झूठी वापसी
    • सही लौटें
• एक फ़ंक्शन को परिभाषित करें string_res() । यह स्ट्रिंग लेगा
  • उत्तर:=0
  • i के लिए 2 से लेकर स्ट्रिंग + 1 के आकार तक, do
    • Ans :=ans + i *(floor value of (i - 1)/2)
    • उत्तर:=उत्तर मॉड 1000000007
  • वापसी और
• अगर str_check(string) सही है, तो
  • रिटर्न string_res(string)
• उत्तर:=0
• odd_list :=एक नई सूची जिसमें एक नई सूची, एक नया नक्शा और 1 शामिल है
• स्ट्रिंग में प्रत्येक s के लिए, करें
  • यदि s विषम_सूची में मौजूद नहीं है[1], तो
    • विषम_सूची[1, s] :=0
  • विषम_सूची[1, s] :=विषम_सूची[1, s] + 1
• i के लिए 0 से लेकर स्ट्रिंग के आकार तक, करें
  • odd_list[0] के अंत में i डालें[0]
• उत्तर:=उत्तर + palindrome_calculator(odd_list[1])
• even_list :=एक नई सूची जिसमें एक नई सूची, एक नया नक्शा और 1 शामिल है
• i के लिए 0 से लेकर स्ट्रिंग के आकार -1 तक के लिए
  • यदि स्ट्रिंग [i] स्ट्रिंग [i + 1] के समान है, तो
    • ईवन_सूची के अंत में i डालें[0]
    • tmp:=string[index i से i + 2]
    • अगर tmp सम_सूची में मौजूद नहीं है[1], तो
      • सम_सूची[1, tmp] :=0
    • सम_सूची[1, tmp] :=सम_सूची[1, tmp] + 1
• उत्तर:=उत्तर + पैलिंड्रोम_कैलकुलेटर (सम_सूची[1])
• श्रेणी 3 से लेकर स्ट्रिंग के आकार तक के वैल के लिए, करें
  • यदि वैल मॉड 2 0 के समान है, तो
    • wt:=सम_सूची
  • अन्यथा,
    • wt:=विषम_सूची
  • new_t :=एक नई सूची जिसमें एक नई सूची, एक नया नक्शा और वैल शामिल हैं
  • wt[0] में प्रत्येक अनुक्रमणिका के लिए, करें
    • यदि अनुक्रमणिका - 1>=0 और अनुक्रमणिका + वैल - 2 <स्ट्रिंग और स्ट्रिंग का आकार [सूचकांक -1] स्ट्रिंग के समान है [सूचकांक + वैल - 2], तो
      • सूचकांक डालें - 1 new_t[0] के अंत में
      • tmp :=string[index index - 1 से index - 1 + val]
      • अगर tmp new_t[1] में मौजूद नहीं है, तो
        • new_t[1, tmp] :=0
      • new_t[1, tmp] :=new_t[1, tmp] + 1
  • उत्तर:=उत्तर + palindrome_calculator(new_t[1])
  • उत्तर:=उत्तर मॉड 1000000007
  • यदि वैल मॉड 2 0 के समान है, तो
    • सम_सूची :=new_t
  • अन्यथा,
    • विषम_सूची :=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'

आउटपुट

5