資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：在給定字串的所有可能子字串集中，找到給定位置處給定字串的子字串
假設我們提供了n個字串：str1、str2、str3、……、strn。現在，假設substri是一個包含stri所有子字串的集合。所有substr集合的並集是substr_union。現在，我們給出了q個查詢，我們需要找到substr_union集合中的第q個元素。集合substr_union按字典序排序，索引從1開始。
因此，如果輸入像字串列表=['pqr'，'pqt']，查詢=[4，7，9]，則輸出將為['pqt'，'qt'，'t']
第一個字串的子字串是subs_str_1 = {p, pq, pqr, q, qr, r}，sub_str_2 = {p, pq, pqt, q, qt, t}。
這兩個集合的並集，或substr_union是{p, pq, pqr, pqt, q, qr, qt, r, t}。
因此，索引4、7和9處的專案分別是'pqt'、'qt'和't'。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式lng_i()。它將接收suff、lng、i作為引數。
- d := 一個包含(suff, lng)的新元組。
- lo := 0
- hi := 0
- 對於d中的每個元組(suf, lng)，執行以下操作：
- 如果lng與null相同，則
- lng := 0
- hi := hi + suf的大小 - lng
- 如果hi - 1與i相同，則
- 返回suf
- 否則，如果hi - 1 > i，則
- 對於從lng到suf大小的列表中的值中的索引p和專案q，執行以下操作：
- 如果lo + p與i相同，則
- 返回suf[從索引0到j+1]
- 如果lo + p與i相同，則
- 對於從lng到suf大小的列表中的值中的索引p和專案q，執行以下操作：
- lo := hi
- 如果lng與null相同，則
- 返回False
- 定義一個函式hlp_ii()。它將接收str1、str2作為引數。
- ub := str1的大小和str2的大小中的最小值。
- cnt := 0
- 對於範圍0到ub中的i，執行以下操作：
- 如果str1[i]與str2[i]相同，則
- cnt := cnt + 1
- 否則，
- 返回cnt
- 返回cnt
- 如果str1[i]與str2[i]相同，則
- t_dict := 一個新的對映。
- suff := 一個新的列表。
- lng := 一個新的列表。
- 對於字串中的每個str，執行以下操作：
對於範圍0到str的大小的i，執行以下操作：
- value := str[從索引i到結尾]
- 如果t_dict中不存在value，則
- t_dict[value] := 1
- 在suff的末尾插入value
- 對列表suff進行排序
- suff_len := suff的大小
- 對於範圍0到suff_len大小的i，執行以下操作：
- 如果i與0相同，則
- 在lng的末尾插入null
- 否則，
- 在lng的末尾插入hlp_ii(suff[i-1]，suff[i])
- 如果i與0相同，則
- res := 一個新的列表。
- 對於q_list中的每個q，執行以下操作：
- 在res的末尾插入(lng_i(suff, lng, q-1))
- 返回res
示例
讓我們看看以下實現，以便更好地理解：
def lng_i(suff, lng, i):
d = zip(suff,lng)
lo = hi = 0
for suf, lng in d:
if lng is None:
lng = 0
hi += len(suf) - lng
if hi - 1 == i:
return suf
elif hi - 1 > i:
for p, q in enumerate(list(range(lng, len(suf)))):
if lo + p == i:
return suf[:q+1]
lo = hi
return False
def hlp_ii(str1,str2):
ub = min(len(str1), len(str2))
cnt = 0
for i in range(ub):
if str1[i] == str2[i]:
cnt += 1
else:
return cnt
return cnt
def solve(strings,q_list):
t_dict = {}
suff = []
lng = []
for str in strings:
for i in range(len(str)):
value = str[i:]
if value not in t_dict:
t_dict[value] = 1
suff.append(value)
suff.sort()
suff_len = len(suff)
for i in range(suff_len):
if i == 0:
lng.append(None)
else:
lng.append(hlp_ii(suff[i-1], suff[i]))
res = []
for q in q_list:
(res.append(lng_i(suff, lng, q-1)))
return res
print(solve(['pqr', 'pqt'], [4, 7, 9]))輸入
['pqr', 'pqt'], [4, 7, 9]
輸出
['pqt', 'qt', 't']
更新於：2021年10月11日
141 次瀏覽
廣告