資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告