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

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

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. Задача 15

•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)

30. Задача 16

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

31. Задача 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)

32. Задача 17

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

33. Задача 18

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

34. Задача 19

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

35. Задача 20

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

36. Задача 21

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

37. Задача 22

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

38. Задача 23

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

39. Задача 24

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

40. Задача 24

•s = open('24_24.txt').read()
•mask = [False] * len(s)
•for i in range(len(s) - 2):
sub = s[i:i+3]
if set(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)

41. Задача 25

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

42. Задача 26

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

43. Ответы

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