查找Python中给定字符串的所有不同回文子字符串
假设我们有一个带有小写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")
输入值
bddaaa
输出结果
a aa b aaa d dd