Python程式：查詢字串中的迴文邊界

假設我們得到一個字串str。字串的邊界是指一個子字串，它是該字串的真字首和字尾。例如，“ab”是字串“ababab”的邊界。如果邊界字串是迴文，則稱該邊界為迴文邊界。現在假設給定字串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作為輸入。
    • ans := 0
    • 對於input_dict值的每個item1、item2，執行以下操作：
      • ans := ans + item2 *(item2 - 1) / 2 的向下取整值
    • 返回ans
  • 定義一個函式str_check()。它將接收字串作為輸入。
    • t_str := 字串[0]
    • 對於字串中的每個s，執行以下操作：
      • 如果s與t_str不同，則
        • 返回False
      • 返回True
  • 定義一個函式string_res()。它將接收字串作為輸入。
    • ans := 0
    • 對於從2到字串大小+1的每個i，執行以下操作：
      • ans := ans + i *(i - 1) / 2 的向下取整值
      • ans := ans mod 1000000007
    • 返回and
  • 如果str_check(string)為True，則
    • 返回string_res(string)
  • ans := 0
  • odd_list := 一個包含一個新列表、一個新對映和1的新列表
  • 對於字串中的每個s，執行以下操作：
    • 如果s不在odd_list[1]中，則
      • odd_list[1, s] := 0
    • odd_list[1, s] := odd_list[1, s] + 1
  • 對於從0到字串大小的每個i，執行以下操作：
    • 將i插入odd_list[0]的末尾
  • ans := ans + palindrome_calculator(odd_list[1])
  • even_list := 一個包含一個新列表、一個新對映和1的新列表
  • 對於從0到字串大小-1的每個i，執行以下操作：
    • 如果string[i]與string[i + 1]相同，則
      • 將i插入even_list[0]的末尾
      • tmp := 從索引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])
  • 對於從3到字串大小的每個val，執行以下操作：
    • 如果val mod 2與0相同，則
      • wt := even_list
    • 否則，
      • wt := odd_list
    • new_t := 一個包含一個新列表、一個新對映和val的新列表
    • 對於wt[0]中的每個索引，執行以下操作：
      • 如果index - 1 >= 0且index + val - 2 < 字串大小且string[index - 1]與string[index + val - 2]相同，則
        • 將index - 1插入new_t[0]的末尾
        • tmp := 從索引index - 1到index - 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 := ans mod 1000000007
    • 如果val mod 2與0相同，則
      • even_list := new_t
    • 否則，
      • odd_list := new_t
  • 返回ans

示例

讓我們看看以下實現以更好地理解

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

更新於： 2021年10月11日

229 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告