用 Python 编写的程序，用于找出字符串中的回文边界

pythonserver side programmingprogramming更新于 2025/12/18 19:24:17

假设我们有一个字符串 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

这些值的总和为 1 + 2 + 1 + 1 = 5。

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 palindrome_calculator() 。这将采用 input_dict
- ans := 0
- 对于 input_dict 值中的每个 item1、item2，执行
  - ans := ans + item2 *(floor value of (item2 - 1) / 2)
- 返回 ans
定义一个函数 str_check() 。这将采用字符串
- t_str := string[0]
- 对于字符串中的每个 s，执行
  - 如果 s 与 t_str 不同，则
    - 返回 False
  - 返回 True
定义一个函数 string_res() 。这将采用字符串
- ans := 0
- 对于 i 在 2 到字符串大小 + 1 的范围内，执行
  - ans := ans + i *(floor value of (i - 1) / 2)
  - ans := ans mod 1000000007
- 返回 ans
如果 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 := 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 := 包含新列表、新映射和 val 的新列表
- 对于 wt[0] 中的每个索引，执行
  - 如果 index - 1 >= 0 且 index + val - 2 < string 的大小，并且 string[index - 1] 与 string[index + val - 2] 相同，则
    - 在 new_t[0] 末尾插入 index - 1
    - tmp := string[从索引 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'))