Статья Автор: Лебедев Дмитрий Алексеевич

Разбор задач

Текстовый файл 24-197.txt содержит строку из заглавных латинских букв X, Y и Z, всего не более чем из 10⁶ символов. Определите максимальное количество идущих подряд троек символов ZXY или ZYX.

# Доступны файлы для чтения: 24-197.txt 
# Решение способом "конечных автоматов"
fname = "24-197.txt" 
s = open(fname).read()
print(len(s), s[:10], s[-10:])
pr1 = "Z" # для проверки 1-го символа
pr2 = ["ZX","ZY"] # для проверки 2-го символа
pr3 = ["ZXY","ZYX"] # для проверки 3-го символа
ans, tek = 0, 0 # Инициализация ответа и текущего значения
fl = False # автомат выключен/не активен  
jj = 0 # длина цепочки подходящих символов
for i in range(len(s)):
  if (fl == False) and (s[i] in pr1) : # включение автомата и переход в ожидание следующего сигнала
      fl = True
      jj = 1
  elif jj == 1 and ((s[i-1] + s[i]) in pr2) : # проверка 2 сигнала, если он ожидается
      jj = 2 # переход к ожиданию следующего сигнала
  elif jj == 2 and  ((s[i-2] + s[i-1] + s[i]) in pr3): # финальная проверка
      tek += 1 # увеличиваем количество текущих 3-грамм
      ans = max(ans, tek) # фиксируем ответ
      fl = False # автомат выключаем/ ставим на паузу
  else : # символ не подходит
      tek = 0 # сброс значения 
      fl = False # автомат выключаем/ ставим на паузу
      jj = 0 
      
print (ans)

Е. Джобс) Текстовый файл 24-209.txt содержит строку из набора A, B, C, D, E, F, всего не более чем из 10⁶ символов. Найдите максимальное количество подряд идущих пар символов АB, CB, BС и BA, стоящих одна за другой и пересекающихся с соседними парами одной буквой. Например, в строке BDEABCBABBD такие пары составляют подстроку ABCBAB = AB + BC + CB + BA + AB, итого 5 пар.

fname = "24-209.txt"
# Доступны файлы для чтения: 24-197.txt 
# Решение способом "конечных автоматов"
fname = "24-209.txt"
s = open(fname).read()
print(len(s), s[:10], s[-10:])
pr1 = "ABC" # для проверки 1-го символа
pr2 = ["AB","CB","BC", "BA"] # для проверки 2-го символа
ans, tek = 0, 0 # Инициализация ответа и текущего значения
fl = False # автомат выключен/не активен 
jj = 0 # длина цепочки подходящих символов
for i in range(len(s)):
  if (fl == False) and (s[i] in pr1) : # включение автомата и переход в ожидание следующего сигнала
      fl = True
      jj = 1
  elif jj == 1 and  ((s[i-1] + s[i]) in pr2): # финальная проверка
      tek += 1 # увеличиваем количество текущих 3-грамм
      ans = max(ans, tek) # фиксируем ответ
      # автомат выключать НЕ НАДО - ждем продолжения
  else : # символ не подходит
      tek = 0 # сброс значения 
      fl = False # автомат выключаем/ ставим на паузу
      jj = 0 # сброс цепочки
      
print (ans)

Текстовый файл 24-210.txt содержит строку из набора A, B, C, D, E, F, всего не более чем из 10⁶ символов. Найдите максимальное количество подряд идущих троек символов ABC, BAC, CAB, CBA, стоящих одна за другой и пересекающихся с соседними тройками одной буквой. Например, в строке BDEABCBABCABBD такие пары составляют подстроку ABCBABCAB = ABC + СBA + ABC + CAB, итого 4 тройки.

# Доступны файлы для чтения: 24-197.txt 
# Решение способом "конечных автоматов"
fname = "24-210.txt" 
s = open(fname).read()
#s ="BDEABCBABCABBD"
print(len(s), s[:10], s[-10:])
pr1 = "ABC" # для проверки 1-го символа
pr2 = ["AB","BA","CA","CB"] # для проверки 2-го символа
pr3 = ["ABC","BAC","CAB", "CBA"] # для проверки 3-го символа
ans, tek = 0, 0 # Инициализация ответа и текущего значения
fl = False # автомат выключен/не активен  
jj = 0 # длина цепочки подходящих символов
for i in range(len(s)):
  if (fl == False) and (s[i] in pr1) : # включение автомата и переход в ожидание следующего сигнала
      fl = True
      jj = 1
  elif jj == 1 and ((s[i-1] + s[i]) in pr2) : # проверка 2 сигнала, если он ожидается
      jj = 2 # переход к ожиданию следующего сигнала
  elif jj == 2 and  ((s[i-2] + s[i-1] + s[i]) in pr3): # финальная проверка
      tek += 1 # увеличиваем количество текущих 3-грамм
      ans = max(ans, tek) # фиксируем ответ
      jj = 1  # разрешаем продолжать учитывае "сцепку"
      #fl = False # автомат выключаем/ ставим на паузу
  else : # символ не подходит
      tek = 0 # сброс значения 
      fl = False # автомат выключаем/ ставим на паузу
      jj = 0 
      
print (ans)

Текстовый файл 24-212.txt содержит строку из символов A, B, C, D и O, всего не более чем из 10⁶ символов. Определите максимальное количество идущих подряд пар символов вида «согласная + гласная».

# Доступны файлы для чтения: 24-212.txt 
# Решение способом "конечных автоматов"
fname = "24-212.txt"
s = open(fname).read()
#s ="COOAADCABODOBADOCACA"
#print(s)
#print(len(s), s[:10], s[-10:])
pr1 = "BCD" # для проверки 1-го символа
pr2 = "AO" # для проверки 2-го символа
ans, tek = 0, 0 # Инициализация ответа и текущего значения
fl = False # автомат выключен/не активен 
jj = 0
for i in range(len(s)):
  if (fl == False) and (s[i] in pr1) : # включение автомата и переход в ожидание следующего сигнала
      fl = True
      jj = 1
  elif jj == 1 and  (s[i] in pr2): # финальная проверка
      tek += 1 # увеличиваем количество текущих 2-грамм
      ans = max(ans, tek) # фиксируем ответ
      jj = 0
      fl = False 
  else : # символ не подходит, то сбрасываем только текущую длину
         # так как для согласной надо оставить включенное состояние
      tek = 0 # сброс значения 
  print(f'{i=} {tek=} {jj=} {fl=} {s[:i+1]} {ans}')
      
      
print (ans)

Прикрепленные файлы
24-197.txt
24-209.txt
24-210.txt
24-212.txt

Печать