資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：計算每個查詢中相似子字串的數量
假設我們有兩個字串 s 和一個查詢集 Q。其中 Q[i] 包含一對 (l, r)，對於 s 從 l 到 r 的每個子字串，我們必須找到 s 從 x 到 y 的子字串的數量，這些子字串是相似的。如果兩個字串 s 和 t 遵循以下規則，則它們是相似的：
它們長度相同
對於每對索引 (i, j)，如果 s[i] 與 s[j] 相同，則必須滿足 t[i] = t[j]，類似地，如果 s[i] 與 s[j] 不相同，則 t[i] 和 t[j] 必須不同。
因此，如果輸入類似於 s = "hjhhbcbk" Q = [(1,2), (2,4)]，則輸出將是 [6, 1]，因為
- 對於第一個查詢，相似的子字串是 "hj"、"jh"、"hb"、"bc"、"cb" 和 "bk"。
- 對於第一個查詢，相似的子字串是 "jhh"
為了解決這個問題，我們將遵循以下步驟：
- fp := 一個新列表
- 定義一個函式 calc_fingerprint()。這將接收 s
- dict := 一個新的字典，並最初插入鍵值對 (s[0], 0)
- fp := "0"
- j := 1
- 對於 i 從 1 到 s 的大小 - 1，執行以下操作：
- 如果 s[i] 不在 dict 中，則
- dict[s[i]] := j
- j = j+1
- fp := fp + dict[s[i]] 的字串表示形式
- 如果 s[i] 不在 dict 中，則
- 返回 fp 的整數形式
- 從主方法中，執行以下操作：
- 如果 s 的大小 > 10，則
- 對於 i 從 0 到 s 的大小 - 10，執行以下操作：
- x := calc_fingerprint(s[從索引 i 到 i+9])
- 將 x 插入 fp 的末尾
- 對於 i 從 0 到 s 的大小 - 10，執行以下操作：
- ret := 一個新列表
- 對於 i 從 0 到 Q 的大小 - 1，執行以下操作：
- (a, b) := Q[i]
- s1 := s 從索引 a-1 到 b-1 的子字串
- k := 0
- 對於 i 從 0 到 s 的大小 - (b-a)，執行以下操作：
- 如果 b-a > 9 且 fp[a-1] 與 fp[i] 不相同，則
- 轉到下一個迭代
- dict := 一個新的空對映
- s2 := s 從索引 i 到 i+(b-a) 的子字串
- 對於 i 從 0 到 b-a，執行以下操作：
- 如果 s2[i] 不在 dict 中，則
- 如果 s1[i] 在 dict 的值中，則
- 退出迴圈
- dict[s2[i]] := s1[i]
- 如果 s1[i] 在 dict 的值中，則
- 如果 dict[s2[i]] 與 s1[i] 不相同，則
- 退出迴圈
- 如果 s2[i] 不在 dict 中，則
- 否則，
- k := k + 1
- 如果 b-a > 9 且 fp[a-1] 與 fp[i] 不相同，則
- 將 k 插入 ret 的末尾
- 返回 ret
示例
讓我們看看以下實現以獲得更好的理解：
fp = []
def calc_fingerprint(s):
dict = {s[0]: 0}
fp = "0"
j = 1
for i in range(1, len(s)):
if s[i] not in dict:
dict[s[i]], j = j, j+1
fp += str(dict[s[i]])
return int(fp)
def solve(s, Q):
if len(s) > 10:
for i in range(0, len(s)-10):
fp.append(calc_fingerprint(s[i: i+10]))
ret = []
for i in range(len(Q)):
a, b = Q[i]
s1 = s[a-1:b]
k = 0
for i in range(len(s)-(b-a)):
if b-a > 9 and fp[a-1] != fp[i]:
continue
dict = {}
s2 = s[i:i+(b-a)+1]
for i in range(b-a+1):
if s2[i] not in dict:
if s1[i] in dict.values(): break
dict[s2[i]] = s1[i]
if dict[s2[i]] != s1[i]: break
else:
k += 1
ret.append(k)
return ret
s = "hjhhbcbk"
Q = [(1,2), (2,4)]
print(solve(s, Q))輸入
"hjhhbcbk", [(1,2), (2,4)]
輸出
[6, 1]
更新於: 2021年10月11日
298 次瀏覽
廣告