โปรแกรมหาเส้นขอบพาลินโดรมในสตริงใน python

สมมติว่าเราได้รับสตริง str เส้นขอบของสตริงคือสตริงย่อยที่เป็นคำนำหน้าที่ถูกต้องและเป็นคำต่อท้ายของสตริงนั้น ตัวอย่างเช่น 'ab' คือเส้นขอบของสตริง 'ababab' เส้นขอบเรียกว่าเส้นขอบพาลินโดรมหากสตริงเส้นขอบคือพาลินโดรม ตอนนี้ สมมติว่ามีจำนวนเส้นขอบพาลินโดรมจำนวน f(str) ในสตริงที่กำหนด str เราต้องหาผลรวมของ f(str_k) สำหรับสตริงย่อยที่ไม่ว่างทั้งหมด str_k ของ str ผลรวมอาจมีขนาดใหญ่ ดังนั้นการดำเนินการแบบโมดูโลสามารถทำได้ 10^9 + 7

ดังนั้น ถ้าอินพุตเป็นเหมือน str ='pqpqp' ผลลัพธ์จะเป็น 5 มีสตริงย่อย 15 สตริง 'pqpqp'; อย่างไรก็ตาม มีเพียง 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
  • สำหรับแต่ละ item1, item2 ในค่าของ input_dict, do
    • ans :=ans + item2 *(floor value of (item2 - 1) / 2)
  • คืนสินค้า
• กำหนดฟังก์ชัน str_check() สิ่งนี้จะใช้สตริง
  • t_str :=string[0]
  • สำหรับแต่ละ s ในสตริง ทำ
    • ถ้า s ไม่เหมือนกับ t_str แล้ว
      • คืนค่าเท็จ
    • คืนค่า True
• กำหนดฟังก์ชัน string_res() สิ่งนี้จะใช้สตริง
  • ตอบ :=0
  • สำหรับ i ในช่วง 2 ถึงขนาดของสตริง + 1 ให้ทำ
    • ans :=ans + i *(ค่าพื้นของ (i - 1) / 2)
    • ans :=แทน mod 1000000007
  • กลับมาและ
• ถ้า str_check(string) เป็น True แล้ว
  • ส่งคืน string_res(สตริง)
• ตอบ :=0
• odd_list :=รายการใหม่ที่มีรายการใหม่ แผนที่ใหม่ และ 1
• สำหรับแต่ละ s ในสตริง ทำ
  • ถ้า s ไม่มีอยู่ใน odd_list[1] แล้ว
    • odd_list[1, s] :=0
  • odd_list[1, s] :=odd_list[1, s] + 1
• สำหรับ i ในช่วง 0 ถึงขนาดของสตริง ให้ทำ
  • แทรก i ที่ส่วนท้ายของ odd_list[0]
• ans :=ans + palindrome_calculator(odd_list[1])
• even_list :=รายการใหม่ที่มีรายการใหม่ แผนที่ใหม่ และ 1
• สำหรับฉันในช่วง 0 ถึงขนาดของสตริง - 1 ทำ
  • ถ้า string[i] เหมือนกับ string[i + 1] แล้ว
    • แทรก i ที่ส่วนท้ายของeven_list[0]
    • tmp :=string[จากดัชนี i ถึง i + 2]
    • ถ้าไม่มี tmp ใน even_list[1] แสดงว่า
      • even_list[1, tmp] :=0
    • even_list[1, tmp] :=even_list[1, tmp] + 1
• ans :=ans + palindrome_calculator(even_list[1])
• สำหรับ val ในช่วง 3 ถึงขนาดของสตริง ให้ทำ
  • ถ้า val mod 2 เหมือนกับ 0 แล้ว
    • wt :=even_list
  • มิฉะนั้น
    • wt :=odd_list
  • new_t :=รายการใหม่ที่มีรายการใหม่ แผนที่ใหม่ และวาล
  • สำหรับแต่ละดัชนีใน wt[0] ให้ทำ
    • ถ้า index - 1>=0 และ index + val - 2 <ขนาดของ string และ string[index - 1] เหมือนกับ string[index + val - 2] แล้ว
      • แทรกดัชนี - 1 ที่ส่วนท้ายของ new_t[0]
      • tmp :=string[จากดัชนีดัชนี - 1 ถึงดัชนี - 1 + val]
      • หากไม่มี tmp ใน new_t[1] แสดงว่า
        • new_t[1, tmp] :=0
      • new_t[1, tmp] :=new_t[1, tmp] + 1
  • ans :=ans + palindrome_calculator(new_t[1])
  • ans :=แทน mod 1000000007
  • ถ้า val mod 2 เหมือนกับ 0 แล้ว
    • even_list :=new_t
  • มิฉะนั้น
    • odd_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'

ผลลัพธ์

5