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

304.13K

Category:

informatics

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

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

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

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

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

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) 35
• 19) 544
• 20) 84
• 21) 8
• 22) 90
• 23) 33
• 24) 23246
• 25) 49
• 26) 17

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

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

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

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

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

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

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

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

48. Задача 27

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

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

50. Задача 28

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

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

52. Задача 29

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

53. Задача 29

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

54. Задача 30

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

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

56. Задача 31

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

57. Задача 32

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

58. Задача 33

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

59. Задача 34

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

60. Задача 35

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

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

62. Задача 36

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

63. Задача 37

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

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

65. Задача 38

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

66. Задача 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 = [0] + inds + [len(s)+1]
•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)

67. Ответы

• 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

English Русский Rules