在 Python 中查找给定字符串的所有不同回文子字符串

server side programmingprogrammingpython

假设我们有一个包含小写 ASCII 字符的字符串，我们必须找到它的所有不同连续回文子字符串。

因此，如果输入为"bddaaa"，则输出将是 [a, aa, aaa, b, d, dd]

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

m := 一个新的映射
n := s 的大小
矩阵 := 制作两行 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 := s 从索引 1 到末尾
m[s[0]] := 1
对于范围从 1 到 n 的 i，执行
- 对于范围从 0 到 1 的 j，执行
  - 对于范围中的 temp，执行
    - m[s 的子字符串从 (i - temp - 1) 到 (i - temp - 1 + 2 * temp + j)] = 1
- m[s[i]] := 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")