資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢字串子串完全匹配或僅有一位差異的索引
假設，我們有兩個字串。第一個字串的長度大於第二個字串，我們需要檢查第一個字串的子串是否與第二個字串完全匹配或僅有一位不同。我們返回第一個字串中子串可能與第二個字串匹配的起始索引。
因此，如果輸入類似於 string1 = 'tpoint'，string2 = 'pi'，則輸出將是 1 2。
第一個字串中與第二個字串匹配或僅有一位不同的子串（索引為 1 和 2）是 'po' 和 'oi'。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 search()。它將接收 string1 和 string2 作為引數。
- str_cat := string1 + string2
- z_list := 一個新的列表，大小與 str_cat 相同，並初始化為 0。
- z_list[0] := str_cat 的大小。
- right := 0
- left := 0
- 對於 i 從 1 到 str_cat 的大小，執行以下操作：
- 如果 i > right，則：
- j := 0
- 當 j + i < str_cat 的大小，並且 str_cat[j] 與 str_cat[j+i] 相同，執行以下操作：
- j := j + 1
- z_list[i] := j
- 如果 j > 0，則：
- left := i
- right := i + j - 1
- 否則：
- k := i - left
- r_len := right - i + 1
- 如果 z_list[k] < r_len 且不為零，則：
- z_list[i] := z_list[k]
- 否則：
- m := right + 1
- 當 m < str_cat 的大小，並且 str_cat[m] 與 str_cat[m - i] 相同，執行以下操作：
- m := m + 1
- z_list[i] := m - i
- left := i
- right := m - 1
- z_list[i] := string1 的大小和 z_list[i] 中的最小值。
- 如果 i > right，則：
- 返回 z_list（從索引 string1 的大小到結尾）。
- fwd := search(str2, str1)
- bwrd := search(str2（從索引 0 到結尾），str1（從索引 0 到結尾）)
- 反轉列表 bwrd。
- idx := 一個新的列表。
- 對於 i 從 0 到 str1 的大小 - (str2 的大小 + 1)，執行以下操作：
- 如果 fwd[i] + bwrd[i + (str2 的大小 - 1)] >= str2 的大小 - 1，則：
- 在 idx 的末尾插入 i 的字串表示形式。
- 如果 fwd[i] + bwrd[i + (str2 的大小 - 1)] >= str2 的大小 - 1，則：
- 如果 idx 的大小為 0，則：
- 返回 False。
- 否則：
- idx 的字串表示形式。
示例
讓我們看看以下實現以更好地理解：
def search(string1, string2):
str_cat = string1 + string2
z_list = [0] * len(str_cat)
z_list[0] = len(str_cat)
right = 0
left = 0
for i in range(1, len(str_cat)):
if i > right:
j = 0
while j + i < len(str_cat) and str_cat[j] == str_cat[j+i]:
j += 1
z_list[i] = j
if j > 0:
left = i
right = i + j - 1
else:
k = i - left
r_len = right - i + 1
if z_list[k] < r_len:
z_list[i] = z_list[k]
else:
m = right + 1
while m < len(str_cat) and str_cat[m] == str_cat[m -i]:
m += 1
z_list[i] = m - i
left = i
right = m - 1
z_list[i] = min(len(string1), z_list[i])
return z_list[len(string1):]
def solve(str1, str2):
fwd = search(str2, str1)
bwrd = search(str2[::-1], str1[::-1])
bwrd.reverse()
idx = []
for i in range(len(str1) - len(str2)+1):
if fwd[i] + bwrd[i+len(str2)-1] >= len(str2)-1:
idx.append(str(i))
if len(idx) == 0:
return False
else:
return (" ".join(idx))
print(solve('tpoint', 'pi'))輸入
'tpoint', 'pi'
輸出
1 2
更新於: 2021年10月11日
164 次瀏覽
廣告