在python中找出字符串中回文边界的程序
假设我们提供了一个字符串str。字符串的边框是一个子字符串，它是该字符串的适当前缀和后缀。例如，'ab'是字符串'ababab'的边框。如果边界字符串是回文，则边界称为回文边界。现在假设f(str)给定字符串str中有回文边界的数量。我们必须找出f(str_k)str的所有非空子串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.
示例
让我们看下面的实现来更好地理解
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