資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 程式：查詢字串與其後綴之間的相似度
假設我們給定一個字串 'input_str'。如果我們確定 'input_str' 中的所有後綴；例如，如果字串是 'abcd'，則字尾為 'abc'、'bcd'、'cd'、'd'。現在，我們透過 'input_str' 和字尾中最長公共字首的長度來檢查 'input_str' 和所有後綴之間的相似度。需要返回 'input_str' 和所有後綴之間相似度的總和。
因此，如果輸入類似於 input_str = 'tpotp'，則輸出將為 7
字串 'tpotp' 的所有後綴為 'tpotp'、'potp'、'otp'、'tp' 和 'p'。
如果我們檢查所有後綴與 input_str 的相似度，則得到 -
'tpotp' similarity 5 'potp' similarity 0 'otp' similarity 0 'tp' similarity 2 'p' similarity 0 Sum of similarities = 5 + 0 + 0 + 2 + 0 = 7.
為了解決這個問題，我們將遵循以下步驟 -
- return_list := 一個包含 input_str 大小的新列表
- i := 1
- p := 0
- q := 0
- r := 0
- 當 i < input_str 的大小 時，執行
- 如果 q < i < (q+p)，則
- 如果 return_list[i-q] >= q+p-i，則
- r := q + p - i
- p := 0
- q := 0
- 否則，
- 將 return_list[i-q] 插入到 return_list 的末尾
- i := i + 1
- r := 0
- 如果 return_list[i-q] >= q+p-i，則
- 否則，
- 當 (i + r < input_str 的大小) 且 (input_str[r] 與 input_str[i+r] 相同) 時，執行
- r := r + 1
- 將 r 插入到 return_list 的末尾
- p := r
- q := i
- i := i + 1
- r := 0
- 當 (i + r < input_str 的大小) 且 (input_str[r] 與 input_str[i+r] 相同) 時，執行
- 如果 q < i < (q+p)，則
- 返回 return_list 中元素的總和
示例
讓我們看看以下實現以更好地理解 -
def solve(input_str):
return_list = [len(input_str)]
i = 1
p, q = 0,0
r = 0
while i < len(input_str):
if q < i < (q+p):
if return_list[i-q] >= q+p-i:
r = q + p - i
p, q = 0, 0
else:
return_list.append(return_list[i-q])
i += 1
r = 0
else:
while i + r < len(input_str) and input_str[r] == input_str[i+r]:
r += 1
return_list.append(r)
p,q = r,i
i += 1
r = 0
return sum(return_list)
print(solve('tpotp'))輸入
'tpotp'
輸出
5
更新於: 2021-10-11
119 次瀏覽
廣告