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

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()
Задача 4
•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

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

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