Алгоритмы для обработки массива символов

Поиск последовательностей из пар (троек)

822.62K

Category:

programming

Занятие 3.4 Алгоритмы для обработки массива символов (24)

1. Алгоритмы для обработки массива символов

2.

•https://clck.ru/3RpYiQ

3. Суть задания

• Это задача на обработку символьных строк и поиск
закономерностей в большом объеме данных (текстовом
файле).
• Дана последовательность символов (обычно заглавные
латинские буквы или цифры), длина которой может
достигать миллиона элементов. Ручной перебор здесь
невозможен.
• Необходимо написать программу, которая
проанализирует файл и найдет экстремальные значения:
максимальную длину непрерывной цепочки, количество
подстрок определенного вида или самый частый символ,
удовлетворяющий сложным условиям (чередование,
ограничения по количеству, маски).

4. Поиск непрерывных цепочек символов

• В этих задачах необходимо найти максимальную длину
подстроки, состоящей из одинаковых символов (AAAA...),
заданного набора (только гласные) или чередующихся
групп (XYZXYZ...).
• Линейный проход. Мы идем по строке один раз,
сравнивая текущий символ с соседом или
шаблоном. Считаем текущую длину (curr) и
обновляем рекорд (max).
• Replace + Split. «Мусорные» символы заменяются
на пробелы, строка разбивается (split), и мы ищем
максимум среди длин получившихся кусков.

5. Пример

Текстовый файл состоит не более чем из 106
символов X, Y и Z. Определите длину самой длинной
последовательности, состоящей из символов X. Хотя
бы один символ X находится в последовательности.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

6. Пример

s = open(‘24_Example.txt').read()
max_count = 0
curr_count = 0
for i in range(len(s)):
if s[i] == "X":
curr_count+=1
else:
max_count = max(max_count, curr_count)
curr_count = 0
max_count = max(max_count, curr_count)
print(max_count) #19

7. Задача 1

• Текстовый файл состоит не более чем из 106
символов A, B и C. Определите максимальное
количество идущих подряд символов A.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

8. Задача 2

• Текстовый файл состоит не более чем из 106
символов X, Y и Z. Определите максимальное
количество идущих подряд символов, среди которых
каждые два соседних различны.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

9. Задача 2

s = open('24_2.txt').read()
max_count = 0
curr_count = 1
for i in range(len(s)-1):
if s[i] != s[i+1]:
curr_count+=1
else:
max_count = max(max_count, curr_count)
curr_count = 1
max_count = max(max_count, curr_count)
print(max_count) # 35

10. Задача 3

• Текстовый файл состоит не более чем из 106
символов A, B и C. Определите максимальное
количество идущих подряд символов, среди которых
каждые два соседних различны.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

11. Задача 4

• Текстовый файл состоит не более чем из 106
символов X, Y и Z. Определите максимальную длину
цепочки вида XYZXYZXYZ... (составленной из
фрагментов XYZ, последний фрагмент может быть
неполным).
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

12. Задача 4

s = open(‘24_4.txt').read()
k=0
k_max = 0
for i in range(len(s)):
if k % 3 == 0 and s[i] == 'X':
k += 1
elif k % 3 == 1 and s[i] == 'Y':
k += 1
elif k % 3 == 2 and s[i] == 'Z':
k += 1
else:
k_max = max(k_max, k)
if s[i] == 'X':
k=1
else:
k=0
k_max = max(k_max, k)
print(k_max) # 13

13. Задача 5

• Текстовый файл состоит не более чем из 106
символов A, B и C. Определите максимальную длину
цепочки вида ABABAB... (составленной из
фрагментов AB, последний фрагмент может быть
неполным).
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

14. Задача 6

• Текстовый файл состоит не более чем из 106
символов L, D и R. Определите максимальное
количество идущих подряд символов, среди которых
каждые два соседних различны.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

15. Задача 7

• Текстовый файл состоит не более чем из 106
символов L, D и R. Определите длину самой
длинной последовательности, состоящей из
символов L. Хотя бы один символ L находится в
последовательности.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

16. Задача 8

• Текстовый файл состоит не более чем из 106
символов L, D и R. Определите максимальную длину
цепочки вида LDRLDRLDR... (составленной из
фрагментов LDR, последний фрагмент может быть
неполным).
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

17. Задача 9

• Текстовый файл содержит строки различной длины.
Общий объём файла не превышает 1 Мбайт. Строки
содержат только заглавные буквы латинского
алфавита (ABC…Z). Определите количество строк, в
которых буква E встречается чаще, чем буква A.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

18. Задача 9

• count = 0
• for s in open(‘24_9.txt'):
if s.count("E") > s.count("A"):
count+=1
• print(count)

19. Задача 10

• Текстовый файл содержит только заглавные буквы
латинского алфавита (ABC…Z). Определите
наибольшую длину цепочки символов, среди
которых нет символов K и L, стоящих рядом.
• Например, в тексте ABCAABAKLD самая длинная
цепочка символов, удовлетворяющая условию, —
ABCAABAK, её длина равна 8.Для выполнения этого
задания следует написать программу. Ниже
приведён файл, который необходимо обработать с
помощью данного алгоритма.

20. Задача 10

• s = open('24_10.txt').readline()
• s = s.replace("KL","K L").replace("LK","L K")
• s = s.split(" ")
• maxlen = 0
• #print(len(max(s, key=len)))
• for i in s:
maxlen = max(len(i), maxlen)
• print(maxlen)

21. Задача 11

• Текстовый файл состоит не более, чем из 107
строчных букв английского алфавита. Найдите
максимальную длину подстроки, в которой символы
a и d не стоят рядом.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

22. Задача 12

23. Ответы

• 1) 7
Ответы
• 2) 35
• 3) 42
• 4) 13
• 5) 24
• 6) 45
• 7) 7
• 8) 15
• 9) 467
• 10) 2796
• 11) 2252
• 12) 1713

24. Задача 13

• Текстовый файл содержит только заглавные буквы
латинского алфавита (ABC...Z). Определите
максимальное количество идущих подряд символов,
среди которых нет ни одной буквы A и при этом не
менее трёх букв E.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

25. Задача 13

• s = open('24_13.txt').read()
• s = s.replace('A'," ")
• a = s.split()
• max_count = 0
• for i in a:
if i.count("E") >= 3:
max_count = max(max_count,len(i))
• print(max_count)

26. Задача 14

• Текстовый файл состоит из символов A, B и C.
• Определите максимальное количество идущих
подряд пар символов AB или CB в прилагаемом
файле.
• Искомая подпоследовательность должна состоять
только из пар AB, или только из пар CB, или только
из пар AB и CB в произвольном порядке следования
этих пар.Для выполнения этого задания следует
написать программу.

27. Задача 14

s = open('24_14.txt').read()
s = s.replace('AB',"*")
s = s.replace('CB',"*")
max_count = 0
curr_count = 0
for i in range(len(s)):
if s[i] == "*":
curr_count+=1
else:
max_count = max(max_count, curr_count)
curr_count = 0
max_count = max(max_count, curr_count)
print(max_count)

28. Задача 15

• Текстовый файл содержит только заглавные буквы
латинского алфавита (ABC…Z). Определите
количество групп из идущих подряд не менее 12
символов, которые начинаются и заканчиваются
буквой E и не содержат других букв E (кроме первой
и последней) и букв F.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

29. Задача 16

• s = open('24_16.txt').read()
• s = s.replace('O',"A").replace('C',"D").replace('F',"D")
• s = s.replace('DA',"*")
• s = s.replace('A'," ").replace('D'," ")
• s = s.split()
• max_count = 0
• for i in s:
max_count = max(max_count, len(i))
• print(max_count)

30. Задача 17

• Текстовый файл состоит из символов A, C, D, F и O.
• Определите максимальное количество идущих
подряд троек символов вида:
• согласная + согласная + гласная.
• Для выполнения этого задания следует написать
программу.

31. Задача 18

• Текстовый файл содержит только буквы A, C, D, F, O.
Определите длину самой длинной цепочки
символов, которая начинается и заканчивается
буквой F, а между двумя последовательными
буквами F содержит не более двух букв A и
произвольное количество других букв.

32. Задача 19

• Текстовый файл состоит не более, чем из 1 200 000
символов английского алфавита.
• Определите максимальное количество идущих
подряд символов, среди которых символы Q, R, S в
различных комбинациях (с учётом повторений) не
стоят рядом.
• Для выполнения этого задания следует написать
программу.

33. Задача 20

• Текстовый файл состоит из символов,
обозначающих прописные буквы латинского
алфавита.
• Определите максимальное количество идущих
подряд символов, среди которых никакие две буквы
из набора букв A, B и C (с учетом повторений) не
записаны подряд.
• Для выполнения этого задания следует написать
программу.

34. Задача 21

• Текстовый файл состоит не более чем из 106
символов арабских цифр (0, 1, ..., 9). Определите
максимальное количество идущих подряд цифр,
расположенных в строгом убывающем порядке.
• Для выполнения этого задания следует написать
программу.

35. Задача 22

• Текстовый файл состоит не более чем из 106
символов арабских цифр (0, 1, ..., 9). Определите
максимальное количество идущих подряд цифр,
среди которых каждые две соседние различны.
• Для выполнения этого задания следует написать
программу.

36. Задача 23

• Текстовый файл состоит не более чем из 106
символов арабских цифр (0, 1, ..., 9). Определите
максимальное количество идущих подряд цифр,
среди которых сумма двух идущих подряд цифр
больше цифры следующего за ними. Для
выполнения этого задания следует написать
программу.

37. Задача 24

• Шифровка содержит только заглавные буквы латинского
алфавита (ABC…Z). Группа из трёх идущих подряд символов,
содержащая по одному разу каждую из букв A, B и C, считается
разделителем. Разделители могут накладываться друг на
друга, например, последовательность символов BCABC
считается идущими подряд разделителями BCA, CAB и ABC.
• При дешифровке разделители удаляются, разбивая шифровку
на фрагменты. Определите количество символов в самом
длинном фрагменте шифровки, полученном после удаления
разделителей.
• Пусть шифровка содержит такие символы:
BADCBACKLMENBCAAA.
• Разделители в этой строке выделены жирным шрифтом.
Шифровка содержит три фрагмента: BAD, KLMEN и AA. Самый
длинный из них содержит 5 символов, в ответе в данном
примере надо записать число 5.

38. Задача 24

s = open('24_24.txt').read()
mask = [False] * len(s)
for i in range(len(s) - 2):
sub = s[i:i+3]
if sorted(sub) == ['A', 'B', ‘C’]:
mask[i] = True
mask[i+1] = True
mask[i+2] = True
max_len = 0
current_len = 0
for i in range(len(s)):
if mask[i] == False:
current_len += 1
else:
max_len = max(max_len, current_len)
current_len = 0
max_len = max(max_len, current_len)
print(max_len)

39. Задача 25

• Текстовый файл состоит из символов,
обозначающих прописные буквы латинского
алфавита. Определите максимальное количество
идущих подряд символов, среди которых никакие
две буквы из набора букв A, B и C (с учетом
повторений) не записаны подряд.

40. Задача 26

• Текстовый файл состоит из заглавных букв
латинского алфавита Q, R, W и цифр 1, 2, 4.
Определите в прилагаемом файле максимальное
количество идущих подряд символов, среди которых
ни одна буква не стоит рядом с буквой, а цифра — с
цифрой. Для выполнения этого задания следует
написать программу.

41. Ответы

• 13) 282
• 14) 65
• 15) 9655
• 16) 95
• 17) 5
• 18) 35
• 19) 544
• 20) 84
• 21) 8
• 22) 90
• 23) 33
• 24) 23246
• 25) 49
• 26) 17

42. Метод индексов и расстояния

В этих задачах необходимо найти длину подстроки,
содержащей определённое количество нужных символов
(например, «ровно 100 букв A» или «не более 5 букв B»),
либо вычислить минимальное/максимальное расстояние
между конкретными буквами.
• Сбор индексов. Вместо перебора всей строки мы
создаем список координат (индексов) только
интересующих нас символов. Это превращает задачу по
обработке текста в математическую задачу с массивом
чисел.
• Вычисление длины. Искомая длина находится как
разность индексов граничных символов (inds[i] - inds[i-k]).
Это позволяет мгновенно вычислять длину подстроки,
пропуская миллионы ненужных символов между
границами.

43. Получение индексов по значению

s = “ACBAABA”
Метод find ищет индекс первого
вхождения символа
index = s.find(‘B’) #2
Метод rfind ищет индекс последнего
вхождения символа
index2 = s.rfind(‘B’) #5

44. Получение индексов по значению

s = “ACBAABA”
Все индексы одного символа:
s = "ACBAABA"
for index, letter in enumerate(s):
if letter == "A":
print(f"Index: {index}, Letter: {letter}")
Index: 0, Letter: A
Index: 3, Letter: A
Index: 4, Letter: A
Index: 6, Letter: A

45. Получение индексов по значению

s = “ACBAABA”
Все индексы одного символа:
s = "ACBAABA"
ind = [i for i,c in enumerate(s) if c == “A”]
print(ind)
[0, 3, 4, 6]

46. Задача 27

• Текстовый файл содержит строки различной длины. Общий объём
файла не превышает 1 Мбайт. Строки содержат только заглавные
буквы латинского алфавита (ABC…Z).В строках, содержащих
менее 25 букв A, нужно определить и вывести максимальное
расстояние между одинаковыми буквами в одной строке.
• Пример. Исходный файл:
• GIGA
• GABLAB
• NOTEBOOK
• AGAAA
• В этом примере во всех строках меньше 25 букв A. Самое
большое расстояние между одинаковыми буквами — в третьей
строке между буквами O, расположенными в строке на 2-⁠
й и 7-⁠
й
позициях. В ответе для данного примера нужно вывести число 5.
• Для выполнения этого задания следует написать программу. Ниже
приведён файл, который необходимо обработать с помощью
данного алгоритма.

47. Задача 27

• s = open('24_27.txt').readlines()
• maxlen = 0
• for line in s:
if line.count("A") < 25:
for letter in line:
maxlen = max(line.rfind(letter) - line.find(letter),
maxlen)
• print(maxlen)

48. Задача 28

• Текстовый файл содержит только заглавные буквы
латинского алфавита (ABC…Z). Определите
максимальное количество идущих подряд символов,
среди которых не более одной буквы A.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

49. Задача 28

• s = open('24_28.txt').readline()
• inds = [i for i,c in enumerate(s) if c == "A"]
• maxlen = 0
• for i in range(len(inds)-2):
lenA = inds[i+2]-inds[i]-1
maxlen = max(maxlen, lenA)
• print(maxlen)

50. Задача 29

• Текстовый файл состоит из символов T, U, V, W, X, Y
и Z.
• Определите в прилагаемом файле максимальное
количество идущих подряд символов (длину
непрерывной подпоследовательности), среди
которых символ Y встречается не более 150 раз.
• Для выполнения этого задания следует написать
программу.

51. Задача 29

• s = open('24_29.txt').readline()
• inds = [i for i,c in enumerate(s) if c == "Y"]
• inds = [-1] + inds + [len(s)]
• maxlen = 0
• for i in range(len(inds)-151):
lenA = inds[i+151]-inds[i]-1
maxlen = max(maxlen, lenA)
• print(maxlen)

52. Задача 30

• Текстовый файл состоит из символов,
обозначающих заглавные буквы латинского
алфавита. Определите минимальное количество
идущих подряд символов, среди которых пара
символов T встречается ровно 150 раз.
• Пример. В строке TTTT пара символов встречается
ровно 3 раза.

53. Задача 30

• s = open('24_30.txt').readline()
• inds = [i for i in range(len(s)-1) if s[i] == "T" and s[i+1] ==
"T"]
• minlen = 10**10
• for i in range(len(inds)-149):
lenA = inds[i+149]-inds[i]+2
minlen = min(minlen, lenA)
• print(minlen)

54. Задача 31

• Текстовый файл состоит не более чем из 106
символов латинского алфавита. Определите длину
самой длинной непрерывной
подпоследовательности, где символ Y встречается
не более 100 раз. Для выполнения этого задания
следует написать программу.

55. Задача 32

• Текстовый файл состоит не более чем из 106
символов латинского алфавита. Определите
минимальную подстроку, содержащую 210 символов
T. Для выполнения этого задания следует написать
программу.

56. Задача 33

• Текстовый файл состоит не более чем из 106
символов латинского алфавита. Определите длину
минимальной подстроки, содержащую не менее 130
символов W. Для выполнения этого задания следует
написать программу.

57. Задача 34

• Текстовый файл состоит не более чем из 106
символов латинского алфавита. Определите
минимальную подстроку, содержащую 100 символов
Т. Для выполнения этого задания следует написать
программу. В ответ запишите длину минимальной
подстроки, содержащую 100 символов Т.

58. Задача 35

• Текстовый файл состоит из символов T, U, V, W, X, Y
и Z. Определите в прилагаемом файле
максимальное количество идущих подряд символов
(длину непрерывной подпоследовательности), среди
которых пара символов W встречается ровно 100
раз.

59. Задача 35

• s = open('24_35.txt').readline()
• inds = [i for i in range(len(s)-1) if s[i] == "W" and s[i+1]
== "W"]
• maxlen = 0
• for i in range(len(inds)-99-2):
lenA = inds[i+99+2]-inds[i]
maxlen = max(maxlen, lenA)
• print(maxlen)

60. Задача 36

• Текстовый файл состоит из символов T, U, V, W, X, Y
и Z.
• Определите в прилагаемом файле максимальное
количество идущих подряд символов (длину
непрерывной подпоследовательности), среди
которых символ T встречается ровно 100 раз.
• Для выполнения этого задания следует написать
программу.

61. Задача 37

• Текстовый файл содержит только заглавные буквы
латинского алфавита (ABC…Z). Определите
максимальную длину непрерывного фрагмента,
который начинается и заканчивается одной и той же
буквой из первой половины алфавита (от A до M) и
не содержит эту букву внутри.

62. Задача 37

• s = open('24_37.txt').readline()
• maxlen = 0
• for letter in "ABCDEFGHIJKLM":
inds = [i for i,c in enumerate(s) if c == letter]
for i in range(len(inds)-1):
lenA = inds[i+1]-inds[i]+1
maxlen = max(maxlen, lenA)
• print(maxlen)

63. Задача 38

• Текстовый файл состоит из заглавных букв
латинского алфавита А, В, C, D, Е и F. Определите
максимальное количество идущих подряд символов
в прилагаемом файле, среди которых пара символов
DE (в указанном порядке) встречается не более 240
раз. Для выполнения этого задания следует
написать программу.

64. Задача 38

• s = open('24_38.txt').readline()
• inds = [i for i in range(len(s)-1) if s[i] == "D" and s[i+1] ==
"E"]
• inds = [-1] + inds + [len(s)]
• maxlen = 0
• for j in range(1,40):
for i in range(len(inds)-j):
lenA = inds[i+j]-inds[i]-1
maxlen = max(maxlen, lenA)
• print(maxlen)

65. Ответы

• 27) 1004
• 28) 337
• 29) 244
• 30) 195560
• 31) 169
• 32) 3844
• 33) 2086
• 34) 1523
• 35) 82167
• 36) 133
• 37) 322
• 38) 970 249

66. Регулярные выражения

Регулярные выражения (regex) - это шаблоны для поиска и
обработки текста. В задании 24 они используются для поиска
цепочек символов по определённым правилам.
• Import re
• chunks = re.findall(r’[X]+', s)

67. Регулярные выражения

• import re
• # Поиск всех совпадений
• re.findall(pattern, string) # Возвращает список всех совпадений
• # Поиск первого совпадения
• re.search(pattern, string) # Возвращает объект Match или None
• # Поиск с итератором
• re.finditer(pattern, string) # Возвращает итератор объектов Match

68. Match

• import re
• s = "Привет 123 мир 456"
• match = re.search(r'[0-9]+', s)
• if match:
print(match.group())
# Найденная подстрока: "123"
print(match.start())
# Индекс начала: 7
print(match.end())
# Индекс конца: 10
print(match.span())
# Кортеж (начало, конец): (7, 10)

69. Символьные классы

• [0-9]
# Любая цифра от 0 до 9
• [A-Z]
# Любая заглавная буква от A до Z
• [a-z]
# Любая строчная буква от a до z
• [A-F]
# Буквы от A до F (часто для шестнадцатеричных чисел)
• [0-3]
# Цифры 0, 1, 2, 3
• [AEIOU] # Только гласные буквы

70. Квантификаторы

• +
# Один или более раз
• *
# Ноль или более раз
• ?
# Ноль или один раз
• {n}
# Ровно n раз
• {n,}
# n или более раз
• {n,m}
# От n до m раз

71. Специальные последовательности

• \d
# Любая цифра (эквивалент [0-9])
• \D
# Любой символ, кроме цифры
• \w
# Буква, цифра или подчёркивание
• \W
# Любой символ, кроме буквы, цифры, подчёркивания
• \s
# Пробельный символ
• \S
# Любой символ, кроме пробельного

72. Регулярные выражения

• import re
• s = open('24.txt').read()
• # Найти все цепочки из букв X
• chunks = re.findall(r’[X]+', s)
• max_length = max(chunks, key=len)

73. Задача 1

74. Задача 1

• import re
• s = open('24_1.txt').read()
• chunks = re.findall(r'[A]+', s)
• max_length = len(max(chunks, key=len))
• print(max_length) #7

75. Пример

76. Поиск последовательностей из пар (троек)

• import re
• s = "ABABAB"
• chunks = re.findall(r'(AB)+', s) #['AB’] ищет только один кусочек.
• chunks = re.findall(r'(?:AB)+', s) # ['ABABAB’] то, что нам нужно.
• ?: указывает питону, что скобки нужны только для работы
квантификатора, нужна вся цепочка

77. Задача 14

78. Задача 14

• import re
• s = open('24_14.txt').read()
• chunks = re.findall(r'(?:AB|CB)+', s)
• max_length = len(max(chunks, key=len))
• print(max_length//2) #65

79. Задача 16

• Текстовый файл состоит из символов A, C, D, F и O.
• Определите максимальное количество идущих
подряд пар символов вида:
• согласная + гласная.
• Для выполнения этого задания следует написать
программу.

80. Задача 16

• import re
• s = open('24_16.txt').read()
• chunks = re.findall(r’(?:[CDF][AO])+', s)
• max_length = len(max(chunks, key=len))
• print(max_length//2) #95

81. Задача 17

82. Задача 4

83. Задача 4

• import re
• s = open('24_4.txt').read()
• chunks = re.findall(r'(?:XYZ)+(?:XY|X)', s)
• max_length = len(max(chunks, key=len))
• print(max_length) #13

84. Задача 5

85. Пересечения

• Найдет ли re.findall все вхождения ABA в строке
ABABA?
• Он найдет первое ABA.
• Потом он "съест" эти 3 символа и пойдет искать
дальше.
• Оставшийся кусок: BA. Второе ABA он не увидит.
• Если задача просит найти количество
пересекающихся комбинаций (например, "сколько
раз встречается XAX"), регулярки лучше не
использовать. Используем цикл for i in range(len(s)2).

86. Задача 39

• Текстовый файл состоит не более чем из 106
символов латинского алфавита. Необходимо найти
самую длинную подстроку, которая может являться
числом в 24-⁠
ричной системе счисления. В ответ
записать длину последовательности символов,
которая может являться числом в 24-⁠
ричной системе
счисления.
• Примечание. Число не может начинаться с нуля!
• 0123456789ABCDEFGHIJKLMN

87. Задача 39

• import re, string
• s = open('24_39.txt').read()
• print(string.ascii_uppercase)
• chunks =
re.findall(r'[0123456789ABCDEFGHIJKLMN]+', s)
• chunks = [i for i in chunks if i[0] != "0"]
• max_length = len(max(chunks, key=len))
• print(max_length) # 40

88. Задача 40

• Текстовый файл состоит из десятичных цифр и
заглавных букв латинского алфавита.
• Определите в этом файле последовательность
идущих подряд символов, представляющих собой
запись максимального чётного 14-ричного числа. В
ответе запишите количество символов (значащих
цифр в записи числа) в этой последовательности.
• Примечание. Латинские буквы A, B, C и D означают
цифры из алфавита 14⁠
-⁠
ричной системы счисления.

89. Задача 40

import re
s = open('24_40.txt').read()
max_num = 0
max_len = 0
chunks =
re.findall(r'[123456789ABCD][0123456789ABCD]*[0246
8AС]', s)
for i in chunks:
if int(i,14)>max_num:
max_num = int(i,14)
max_len = len(i)
print(max_len) #2598

90. Метод частотного словаря

• Суть подхода. В этих задачах необходимо определить,
какой символ (или подстрока) встречается чаще/реже
всего, найти элементы с заданной частотой, либо
подсчитать количество различных элементов в тексте.
• Построение словаря. Вместо многократного прохода по
строке в поисках каждого символа мы за один проход
строим словарь, где ключ — символ (или подстрока), а
значение — количество его вхождений. Это превращает
задачу по обработке текста в задачу по анализу готовой
таблицы частот.
• Извлечение ответа. Искомый результат находится
стандартными операциями над словарём: max(freq,
key=freq.get) для самого частого элемента, фильтрация
freq[k] == n для элемента с нужной частотой, len(freq) для
количества различных элементов. Это позволяет
мгновенно получить ответ, не перебирая текст повторно.

91. Словарь

• Список - хранит элементы по порядку, доступ по
числовому индексу (0, 1, 2...).
• Словарь - хранит пары «ключ: значение», доступ по
ключу.
• freq = {'A': 5, 'B': 3, 'C': 8}
• freq['A'] # 5

92. Counter

• Counter - специальный словарь из модуля collections,
который сам считает количество вхождений каждого
элемента.
• from collections import Counter
• freq = Counter("AABBBCCCC")
• # Counter({'C': 4, 'B': 3, 'A': 2})
• freq.most_common(1) # [('C', 4)] — самый частый
• freq.most_common()[-1] # ('A', 2) — самый редкий
• freq['B'] # 3 — частота конкретного элемента

93. Задача 41

• Текстовый файл содержит только заглавные буквы
латинского алфавита (ABC…Z). Определите символ,
который чаще всего встречается в файле сразу
после буквы A.
• Например, в тексте ABCAABADDD после буквы A
два раза стоит B, по одному разу — A и D. Для этого
текста ответом будет B.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

94. Задача 41

• from collections import Counter
• s = open('24_41.txt').read()
• st = ""
• for i in range(len(s)-1):
if s[i] == "A":
st += s[i+1]
• freq = Counter(st)
• print(freq.most_common(1)) #G

95. Задача 42

• Текстовый файл содержит только заглавные буквы
латинского алфавита (ABC…Z). Определите символ,
который чаще всего встречается в файле между
двумя одинаковыми символами.
• Например, в тексте CBCABABACCC есть
комбинации CBC, ABA (два раза), BAB и CCC. Чаще
всего — 3 раза — между двумя одинаковыми
символами стоит B, в ответе для этого случая надо
написать B.
• Для выполнения этого задания следует написать
программу. Ниже приведён файл, который
необходимо обработать с помощью данного
алгоритма.

96. Задача 42

• from collections import Counter
• s = open('24_41.txt').read()
• st = ""
• for i in range(len(s)-2):
if s[i] == s[i+2]:
st += s[i+1]
• freq = Counter(st)
• print(freq.most_common(1)) #G

97. Задача 43

• Текстовый файл содержит строки различной длины.
Общий объём файла не превышает 1 Мбайт. Строки
содержат только заглавные буквы латинского
алфавита (ABC…Z).Необходимо найти строку,
содержащую наименьшее количество букв G (если
таких строк несколько, надо взять ту, которая
находится в файле раньше), и определить, какая
буква встречается в этой строке чаще всего. Если
таких букв несколько, надо взять ту, которая позже
стоит в алфавите.

98. Задача 43

• from collections import Counter
• f = open('24_43.txt').readlines()
• mn = 10**20
• letters = []
• for i in f:
if i.count('G') < mn:
mn = i.count('G')
freq = Counter(i)
max_count = max(freq.values())
letters = [k for k, v in freq.items() if v == max_count]
• print(letters) # T

99. Задача 44

• Текстовый файл содержит строки различной длины, содержащие
только заглавные буквы латинского алфавита (ABC…Z). В каждой
строке файла определяется буква, которая чаще всего стоит сразу
после буквы A, эта буква заносится в отдельный список. Если
несколько разных букв встречаются в строке сразу после A
одинаковое максимальное количество раз, в список заносятся все
эти буквы. Определите, сколько раз встретится в этом списке
самая частая в нём буква.
• Пример.
• Пусть файл содержит такие строки:
• ABBAAABBABBXY
• XYAYYXYABA
• Здесь в первой строке сразу после A три раза стоит B и два раза
A. Чаще других стоит B, эта буква попадает в отдельный список.
• Во второй строке после A по одному разу стоят буквы Y и B, обе
эти буквы попадают в список.
• В итоге буква B попадает в список два раза, буква Y — один раз.
Чаще других в списке встречается буква B — два раза. В ответе
для этого примера надо записать число 2.

100. Задача 44

from collections import Counter
f = open('24_44.txt').readlines()
mn = 10**20
letters = ""
for s in f:
current_letters=""
for i in range(len(s)-1):
if s[i] == "A":
current_letters += s[i+1]
freq = Counter(current_letters)
max_count = max(freq.values())
for k, v in freq.items():
if v == max_count:
letters += k
print(Counter(letters).most_common(1)) # 82

101. Задача 45

• Текстовый файл содержит строки различной длины,
содержащие только заглавные буквы латинского
алфавита (ABC..Z). Будем называть цепочкой группу
идущих подряд одинаковых букв в одной строке.
Определите, сколько раз буква, образующая самую
длинную цепочку в файле, встречается в строке,
содержащей эту цепочку. Если в файле есть
несколько цепочек одинаковой максимальной
длины, нужно выбрать ту из них, для которой общее
количество образующих цепочку букв в
соответствующей строке будет больше.

102. Задача 45

from collections import Counter
f = open('24_45.txt').readlines()
max_len = 0
max_count = 0
for s in f:
i=0
freq = Counter(s)
while i < len(s):
char = s[i]
current_len = 1
while i + current_len < len(s) and s[i + current_len] == char:
current_len += 1
current_count = freq[char]
if current_len > max_len:
max_len = current_len
max_count = current_count
elif current_len == max_len and current_count > max_count:
max_count = current_count
i += current_len
print(max_count) # 45

103. Два указателя

• Метод двух указателей - это алгоритм, который позволяет
найти искомую подстроку за один проход по строке,
вместо долгого перебора вложенными циклами
• Суть метода:
• Есть «окно», которое скользит по строке. У окна есть две
границы (два указателя):
• 1. Правый указатель (r) постоянно идет вперед, расширяя
окно и захватывая новые символы.
• 2. Левый указатель (l) подтягивается слева и сужает окно,
только если условие задачи нарушилось (например, в
окне стало слишком много запрещенных символов).

104. Два указателя

• Например нужно найти максимальную цепочку, в которой
будет ровно 2 буквы «A».
• Мы будем двигаться Правым указателем (r), считая
количество букв A. Пока их 0.
r
B
B
A
C
C
A
Z
Z
Z
A
O
0
1
2
3
4
5
6
7
8
9
10 11
l
O
O
O
A
T
A
B
12 13 14 15 16 17