在Python中找出字符串中的回文边界的程序

在Python中找出字符串中的回文边界的程序

假设我们提供一个字符串str。字符串的边界是一个既是该字符串的前缀又是其后缀的子字符串。例如,’ab’是字符串’ababab’的边界。如果边界字符串是回文字符串,那么该边界称为回文边界。现在假设给定字符串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

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

为了解决这个问题,我们将按照以下步骤进行操作:

  • 定义函数 palindrome_calculator()。它将接收输入参数 input_dict。
    • ans := 0
    • 对于 input_dict 中的每个 item1 和 item2,执行以下步骤:
      • ans := ans + item2 *(item2 – 1 的下整数)
    • 返回 ans
  • 定义函数 str_check()。它将接收 string 参数。
    • t_str := string 的第一个字符
    • 对于 string 中的每个字符 s,执行以下步骤:
      • 如果 s 与 t_str 不同,则
      • 返回 False
      • 返回 True
  • 定义函数 string_res()。它将接收 string 参数。
    • ans := 0
    • 对于 i 在范围从 2 到 string 大小加 1 中,执行以下步骤:
      • ans := ans + i *(i-1 的下整数)
      • ans := ans mod 1000000007
    • 返回 ans
  • 如果 str_check(string) 返回 True,则
    • 返回 string_res(string)
  • ans := 0
  • odd_list := 包含一个新列表、一个新映射和 1 的新列表
  • 对于 string 中的每个字符 s,执行以下步骤:
    • 如果 s 不在 odd_list[1] 中,则
      • odd_list[1, s] := 0
    • odd_list[1, s] := odd_list[1, s] + 1
  • 对于 i 在范围从 0 到 string 大小中,执行以下步骤:
    • 将 i 插入 odd_list[0] 的末尾
  • ans := ans + palindrome_calculator(odd_list[1])
  • even_list := 包含一个新列表、一个新映射和 1 的新列表
  • 对于 i 在范围从 0 到 string 大小减 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 到 string 大小中,执行以下步骤:
    • 如果 val 对 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] 相同,则
      • 将 index – 1 插入 new_t[0] 的末尾
      • 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 对 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程