Задача следующая:
Найдите и вычислите сумму всех возможных подстрок в заданной входной мастер-строке s, из которых можно составить слово «тира» (сокращение от курса), дополнительно удалив ненужные буквы.
ПРИМЕР, возвращаемое значение 11 при вводе "tixratiyra": 1: тихратийра, 2: тихратийра, 3: тихратийра, 4: тихратийра, 5: тихратийра, 6: тихратийра, 7: тихратийра, 8: тихратийра, 9: тихратийра, 10: тихратийра, 11: тихратийра.
Я могу создать рабочий фрагмент кода, но он не будет работать достаточно быстро, он должен выполнить эту задачу за время O (n) с максимальной длиной ввода 10 ^ 5.
Мой код работает мучительно медленно:
def count(s):
start = timeit.default_timer()
c = "bcdefghjklmnopqsuvwxyz"
last_char = ""
indexes = set()
unique_indexes = []
last_A = s.rfind("a")
last_R = s.rfind("r", 0, last_A)
last_I = s.rfind("i", 0, last_R)
last_T = s.rfind("t", 0, last_I)
unique_tiras = ""
for i in range(len(s)):
char = s[i]
if char not in c:
if char == "t":
if i <= last_T:
indexes.add("t")
last_char = "t"
unique_tiras += str(i) + "t"
elif char == "i" and last_char != "i":
if i <= last_I and "t" in indexes:
indexes.add("i")
last_char = "i"
unique_tiras = unique_tiras.replace("t", "i")
elif char == "r" and last_char != "r":
if i <= last_R and ("t" and "i") in indexes:
indexes.add("r")
last_char = "r"
unique_tiras = unique_tiras.replace("i", "r")
elif char == "a":
if i <= last_A and ("t" and "i" and "r") in indexes:
last_char = "a"
unique_tiras = unique_tiras.replace("r", f"-{i};")
pairs = unique_tiras.split(";")
unique_tiras = ""
for elements in pairs:
if "-" in elements:
Tindex = elements.split("-")
unique_indexes.append((int(Tindex[0]), int(Tindex[1])))
unique_tiras += Tindex[0] + "r"
else:
unique_tiras += elements
if len(unique_indexes) < 1:
print("found no tira substrings with input '", s[0:20], "'")
print("indexing took a total of", timeit.default_timer()-start, "s")
return 0
print("found a total of", len(unique_indexes), "tira substrings with input '", s[0:20], "'") #, which are the following:
#print(unique_indexes)
print("indexing took a total of", timeit.default_timer()-start, "s")
start = timeit.default_timer()
unique_substrings = set()
for tiras in unique_indexes:
begin = 0
while begin <= tiras[0]:
end = tiras[1]
while end <= len(s) - 1:
unique_substrings.add((begin, end))
end += 1
begin += 1
print("calculating suitable substrings took a total of", timeit.default_timer()-start, "s")
print("found suitable substrings a total of")
return len(unique_substrings)
if __name__ == "__main__":
print(count("ritari")) # 0
print(count("taikurinhattu")) # 4
print(count("ttiirraa")) # 4
print(count("tixratiyra")) # 11
print(count("aotiatraorirratap")) # 42
Если основная строка состоит из 1e5 символов, а прямо посередине находится искомая последовательность 'tira'
, и эти буквы больше нигде в основной строке не встречаются, сколько в ней подстроки?
Сам ответ не O(n). Больше похоже на O(n²). Например, для строки «xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtiraxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx»
ответ заключается в том, что вы можете выбрать 40 различных начал для вашей подстроки и 40 различных концов (всего 39 x. Таким образом, вы можете включить от 0 до 39 x в качестве префикса и от 0 до 39 x в качестве суффикса). Что приводит к 1600 возможным подстрокам.
С «тирой» посередине это примерно (n/2)².
Моя точка зрения здесь не в том, чтобы сказать «это невозможно». Возможно. Я собираюсь это сделать :D.
Я хочу сказать, что это невозможно, если перечислить все возможности. Потому что, если вы просто пробуете множество подстрок и считаете действительные, вам нужно попробовать как минимум все рабочие решения (плюс нерабочее). И даже если предположить, что вы можете проверить гипотезу за O(1) (чего вы, вероятно, не можете), это означает, что время вычисления должно быть как минимум таким же, как и результат.
Таким образом, мы должны оценить количество рабочих подстрок, фактически не перечисляя и не проверяя их.
Вот мой шанс на это
def minIndex(s, sub):
if not sub[0] in s:
return None,None
i0=s.index(sub[0])
ix=i0
for c in sub[1:]:
ss=s[ix+1:]
if not c in ss:
return None, None
ix=ss.index(c)+ix+1
return i0, ix
def mycount(s, sub):
tot=0
while True:
a,b=minIndex(s, sub)
if a is None:
return tot
tot+=(a+1)*(len(s)-b)
s=s[a+1:]
return tot
def count(s):
return mycount(s, "tira")
if __name__ == "__main__":
print(count("ritari")) # 0
print(count("taikurinhattu")) # 4
print(count("ttiirraa")) # 4
print(count("tixratiyra")) # 11
print(count("aotiatraorirratap")) # 42
То, что я здесь делаю, это какой-то жадный алгоритм (но точный). Итак, я ищу минимальный индекс «t» в строке и минимальный индекс «a», который следует за «t» (с другими буквами между ними).
И это дает мне, используя предыдущее рассуждение на моем примере «xxxxtiraxxxxx», ряд комбинаций.
Обратите внимание, что это делается за O(b), где b — указанный индекс.
Затем, из-за возможности наличия нескольких букв «т», каждая из которых связана с потенциально разным окончанием «а», Я пересчитываю то же самое из всех возможных отправных точек после этой 1-й буквы «t». Потом после 3-го. ... Пока нет ответа.
Например, для s='xxxxxtitrairaxxxxx'
minIndex(s, 'tira')
есть (5,9)
. Это означает, что для того, чтобы «тира» начиналась с первого t, у нас есть 6 возможных отправных точек (0,1,2,3,4,5). И для каждой начальной точки у нас есть len(s)-9
=9 конечных точек (что имеет смысл: после первого возможного окончания a у нас есть iraxxxxx
, то есть 8 букв. Мы можем включить от 0 до 8 из них в качестве суффикса подстроки).
В дополнение к тем 6*9=54 возможностям, которые начинаются с первого t, мы должны рассмотреть и те, которые не включают. Итак, мы просто должны сделать то же самое с s='itrairaxxxxx'
.
У нас есть 1 буква перед первой t
. И за первой возможной a
(которая не такая, как раньше: первая a
была возможным окончанием раньше. Но начиная со второй t
уже нет, и любая рабочая подстрока теперь должна включать и вторую a
), за ней следует 5 x
. Итак, это 2 возможных префикса (i
или ничего) и 6 возможных суффиксов (``, x
, xx
, xxx
, xxxx
, xxxxx
). Итак, 12.
Опять же, как только это будет сделано, мы пробуем то, что можем, без второго запуска t
. Итак, мы повторяем попытку с 'rairaxxxxx'
. Это ничего не дает. Конец расчета.
Окончательный ответ: 54+12 = 66.
Каждый этап вычислений частично повторяет всю строку. В целом это O(n).
Ну, не совсем O(n), в худшем случае. Но это потому, что я был немного ленив.
например со строкой
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttira
, как есть, мой алгоритм O(n²): каждый t
является итерацией в mycount
цикле while. И minIndex
, поскольку единственная буква a находится в самом конце, должна перебирать всю строку, чтобы найти ее индекс. Так что в таком случае это O (n²) (даже если это кажется O (n), потому что этот внутренний O(n)
находится внутри .index()
кода, который является внутренним, вероятно, кодом C, так что очень-очень быстро, сравните остальные чистого кода Python).
Но этого можно избежать: я мог бы запомнить положение первых i
, r
и a
. И пересчитывать позицию индекса a
только тогда, когда мы прошли этот первый i
, пропуская t
(и даже когда мы это делаем, также проверяем, что мы прошли первый r
при поиске другого i
и т. д.).
И это гарантирует, что это действительно O (n) (потому что либо вам нужно постоянно обновлять первое a
, но тогда это означает, что оно близко к первому t
, а общий алгоритм равен O (n) — O(n×len('tira')) чтобы быть точным ; или нет, и тогда вычисление этого .index('a')
выполняется всего несколько раз, и алгоритм тоже O(n)).
В любом случае, с практической точки зрения этот алгоритм намного быстрее вашей версии, и вам не нужно перечислять и проверять возможные решения, чтобы их подсчитать.
Например, для "x"*1000 + "tira" + "x"*1000
ваш код занимает 0,54 секунды, а этот — 4,5 мкс.
Для аварийного теста (наихудший сценарий для моего алгоритма) s = "t"*10000+"ira"
ваш код занимает 31,7 секунды, мой — 35 мс.
Спасибо, это работает фантастически! Действительно полезно, это задание было для меня мучительно сложным по сравнению с другими в этом курсе. Большое спасибо!
Кажется тяжелым. Наивно, для каждой возможной подстроки len(s)+ сколько букв каждой буквы s есть (в правильном порядке)? Может быть, лучше подсчитать, сколько каждой буквы s находится в основной строке, а затем заняться математикой - вам нужно будет сохранить индексы, чтобы убедиться, что буквы в порядке. Это должно как минимум сократить пространство поиска.