数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学用 Python 查找给定字符串中所有不同的回文子串
假设我们有一个包含小写 ASCII 字符的字符串，我们需要找到它所有不同的连续回文子串。
因此，如果输入类似于“bddaaa”，则输出将为 [a, aa, aaa, b, d, dd]
为了解决这个问题，我们将遵循以下步骤：
- m := 新建一个映射
- n := s 的大小
- matrix := 创建一个包含 n 个 0 的两行矩阵
- s := “@” 连接 s 连接 “#”
- 对于 j 从 0 到 1，执行：
- temp := 0
- matrix[j, 0] := 0
- i := 1
- 当 i <= n 时，执行：
- 当 s[i - temp - 1] 等于 s[i + j + temp] 时，执行：
- temp := temp + 1
- matrix[j, i] := temp
- k := 1
- 当 (matrix[j, i - k] 不等于 temp - k) 且 k < temp 时，执行：
- matrix[j,i+k] := matrix[j, i-k] 的最小值
- k := k + 1
- temp := temp - k 与 0 的最大值
- i := i + k
- 当 s[i - temp - 1] 等于 s[i + j + temp] 时，执行：
- s := s 从索引 1 到结尾
- m[s[0]] := 1
- 对于 i 从 1 到 n，执行：
- 对于 j 从 0 到 1，执行：
- 对于 temp 范围内的值，执行：
- m[s 从 (i - temp - 1) 到 (i - temp - 1 + 2 * temp + j) 的子串] = 1
- 对于 temp 范围内的值，执行：
- m[s[i]] := 1
- 对于 j 从 0 到 1，执行：
- 对于 m 中的每个 i，执行：
- 显示 i
示例
让我们来看下面的实现，以便更好地理解：
def find_substr(s):
m = dict()
n = len(s)
matrix = [[0 for x in range(n+1)] for x in range(2)]
s = "@" + s + "#"
for j in range(2):
temp = 0
matrix[j][0] = 0
i = 1
while i <= n:
while s[i - temp - 1] == s[i + j + temp]:
temp += 1
matrix[j][i] = temp
k = 1
while (matrix[j][i - k] != temp - k) and (k < temp):
matrix[j][i+k] = min(matrix[j][i-k], temp - k)
k += 1
temp = max(temp - k, 0)
i += k
s = s[1:len(s)-1]
m[s[0]] = 1
for i in range(1,n):
for j in range(2):
for temp in range(matrix[j][i],0,-1):
m[s[i - temp - 1 : i - temp - 1 + 2 * temp + j]] = 1
m[s[i]] = 1
for i in m:
print (i)
find_substr("bddaaa")输入
bddaaa
输出
a aa b aaa d dd
更新于：2020年8月28日
353 次浏览
广告