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

Z时代
2024-01-10
分类：综合

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

因此，如果输入类似于“ bddaaa”，则输出将为[a，aa，aaa，b，d，dd]

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

m：=新映射
n：= s的大小
矩阵：=生成两行n为0的数
s：=“ @”串联s串联“#”
对于j在0到1的范围内，执行

而s [i-temp-1]与s [i + j + temp]相同，
矩阵[j，i]：=温度
k：= 1
而（矩阵[j，i-k]与temp-k不相同）并且k <temp，
temp：=最高温度-k，0
i：= i + k
温度：=温度+ 1
matrix [j，i + k]：=矩阵[j，ik]的最小值
k：= k + 1

温度：= 0
矩阵[j，0]：= 0
我：= 1
当我<= n时

s：= s从索引1到结束
m [s [0]]：= 1
对于1到n范围内的i

对于温度范围，
m [s的子串，从(i-temp-1)到（i-temp-1 + 2 * temp + j）] = 1
对于j在0到1的范围内，执行
m [s [i]]：= 1

为我每米，做

显示我

示例

让我们看下面的实现以更好地理解-

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")