Giả sử chúng ta có một chuỗi chứa các ký tự ASCII thường, chúng ta phải tìm tất cả các xâu con palindrome liên tục phân biệt của nó.
Ví dụ, nếu đầu vào là "bddaaa", thì đầu ra sẽ là [a, aa, aaa, b, d, dd].
Giải pháp sử dụng thuật toán Manacher biến thể:
- m = dict(), n = len(s)
- matrix = 2 hàng x (n+1) cột fill 0
- s = "@" + s + "#"
- Với j=0,1: temp=0, matrix[j][0]=0, i=1; while i<=n: while s[i-temp-1]==s[i+j+temp]: temp++; matrix[j][i]=temp; k=1; while matrix[j][i-k]!=temp-k and k
- s = s[1:-1]; m[s[0]]=1
- for i=1..n-1: for j=0,1: for temp từ matrix[j][i] down to 1: m[s[i-temp-1 : i-temp-1+2*temp+j]] = 1; m[s[i]]=1
- In các key của m
Ví dụ
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")
Đầu vào
bddaaa
Đầu ra
a aa b aaa d dd