n개의 문자열이 제공된다고 가정합니다. str1, str2, str3,.....,strn. 이제 substri가 stri의 모든 부분 문자열을 포함하는 집합이라고 가정해 보겠습니다. 모든 substr 집합의 합집합은 substr_union입니다. 이제 q개의 쿼리가 주어지고 set substr_union의 q번째 요소를 찾아야 합니다. set 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() 함수를 정의합니다. 이것은 충분할 것입니다, lng, i
- d :=(suff, lng)를 포함하는 새 튜플
- lo :=0
- 안녕하세요 :=0
- d의 각 튜플(suf, lng)에 대해 다음을 수행합니다.
- lng가 null과 유사하면
- 길이 :=0
- hi :=hi + suf - lng의 크기
- hi - 1이 i와 같으면
- 반환
- 그렇지 않으면 hi - 1> i, then
- lng에서 suf 크기까지의 값 목록에서 인덱스 p와 항목 q에 대해
- lo + p가 i와 같으면
- return suf[인덱스 0에서 j+1까지]
- lo + p가 i와 같으면
- lng에서 suf 크기까지의 값 목록에서 인덱스 p와 항목 q에 대해
- 로 :=안녕하세요
- lng가 null과 유사하면
- 거짓을 반환
- 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에 대해
- 값 :=str[인덱스 i에서 끝까지]
- t_dict에 값이 없으면
- t_dict[값] :=1
- 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)) 삽입
- 반환 결과
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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']