Dmustache
@Dmustache
Python, Cpp, SQL

Как вывести самую длинную цепочку из символов в алфавитном порядке?

Задание:
Файл содержит 100000 заглавных латинских букв. Найдите подпоследовательность подряд идущих букв, которые при этом расположены по неубыванию в алфавитном порядке (например, в ABCABA это последовательности A, B, C, A, B, A, AB, ABC, BC, AB). В ответе укажите самую длинную из встреченных в файле последовательностей. Если последовательностей такой длины встречается несколько, укажите первую.
(При этом могут встречаться последовательности типа: ABBBCCCDEEFFFF )
Файл
Мой код:
with open('file.txt', mode='r', encoding='utf-8') as f:
    text = f.read()

lst = [chr(i) for i in range(ord('A'), ord('Z') + 1)]
abc = ''.join(lst) #алфавит

elems = [] #последовательности
for i in range(len(text) - 1):
    passer = False
    elems.append(text[i])
    j = 1
    while passer == False:
        if len(text) < i + j + 1:
            passer = True
        else:
            if ord(text[i + j]) - ord(elems[-1][-1]) < 2:
                elems[-1] += text[i + j]
            else:
                passer = True
        j += 1
print(max(elems, key=len))

не понимаю, почему проходят последовательности символов, аналогичные этой - FCDBCDEFCDDDEDDBAAA
  • Вопрос задан
  • 146 просмотров
Решения вопроса 1
@o5a
Проблема из-за условия проверки
if ord(text[i + j]) - ord(elems[-1][-1]) < 2
в условии последовательности требуется, чтобы последующая буква была не меньше предыдущей, не понятно, с чего Вы вдруг такое условие написали.

Вообще нет надобности сохранять куда-то сами последовательности, тем более, что требуется только первую из самых длинных. Как можно это сделать:
Проходим по символам последовательности и проверяем, стал ли ord() текущего символа меньше предыдущего. Если стал, то последовательность закончилась. Проверяем, не стала ли эта последовательность больше предыдущей. Если да, обновляем данные максимальной последовательности (стартовую позицию и длину).
В противном случае переходим к следующему.
Примерно так:
spoiler
text = ...
text_len = len(text)
max_len = 0
max_idx = 0
seq_idx = 0
prev = 0

for i, x in enumerate(text):
    if ord(x) < prev:
        seq_len = i-seq_idx
        if seq_len > max_len:
            max_len = seq_len
            max_idx = seq_idx
        seq_idx = i
    elif i==text_len-1:
        seq_len = i-seq_idx+1
        if seq_len > max_len:
            max_len = seq_len
            max_idx = seq_idx
    prev = ord(x)
print(max_len, text[max_idx:max_idx+max_len])
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
MinTnt
@MinTnt
Любитель однострочников (Версия 1.106)
Ну в принципе, это можно решить через regex
import re
from string import ascii_uppercase as as_up

print(max(re.findall('*'.join(as_up)+'*', s), key=len))
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы