Самая длинная цепочка символов «С»

· пусть требуется найти самую длинную цепочку символов С (или каких-то других, в соответствии с заданием) в символьной строке s;

· можно использовать такой алгоритм:

while не конец строки:

найти очередную букву C

длина:= длина текущей цепочки букв C

if длина > максимальной длины:

максимальная длина:= длина

однако этот алгоритм содержит вложенный цикл и при составлении программы легко запутаться и не учесть какой-то особый случай (например, когда строка состоит только из букв С)

· лучше применить однопроходный алгоритм без вложенного цикла

for c in s:

обработать символ c

· будем использовать переменные

cLen – длина текущей цепочки букв C

maxLen – максимальная длина цепочки букв C на данный момент

· рассмотрим очередной символ строки; если это буква C, увеличиваем cLen на 1 и, если нужно запоминаем новую максимальную длину; если это не буква C, просто записываем с cLen ноль:

maxLen = 0

cLen = 0

for c in s:

if c == 'C':

cLen += 1     # ещё одна буква C

if cLen > maxLen: # возможно, новая максимальная длина

  maxLen = cLen

else:

cLen = 0      # цепочка букв C кончилась

· проверим правильность работы алгоритма в особых случаях:

а) если вся строка состоит из букв C, значение переменной cLen постоянно увеличивается и в конце станет равно длине символьной строки; то же значение окажется и в переменной maxLen;

б) если в строке нет символов C, переменная cLen всегда равна 0, такое же значение будет и в переменной maxLen

Самая длинная цепочка любых символов

· теперь поставим задачу найти самую длинную цепочку символов в символьной строке s; сложность состоит в том, что мы (в отличие от предыдущей задачи) не знаем, из каких именно символов состоит самая длинная цепочка

· если символов в алфавите немного (скажем, A, B и С), то можно с помощью описанного выше алгоритма найти самые длинные цепочки из букв A, B и C, а затем выбрать из них «длиннейшую»; такая идея может сработать при аккуратной реализации, но плохо обобщается на случай, когда возможных символов много (например, используются все заглавные латинские буквы и цифры) 

· поэтому лучше применить однопроходный алгоритм без вложенного цикла

· будем использовать переменные

curLen – длина текущей цепочки одинаковых символов

maxLen – максимальная длина цепочки одинаковых символов на данный момент

c – символ, из которого строится самая длинная подцепочка

· в начальный момент рассмотрим один первый символ (цепочка длины 1 есть всегда!):

maxLen = 1

curLen = 1

c = s[0]

· будем перебирать в цикле все символы, начиная с s[1] (второго по счёту) до конца строки, постоянно «оглядываясь назад», на предыдущий символ

for i in range(1,len(s)):

обработать пару символов s [ i -1] и s [ i ]

· если очередной символ s[i] такой же, как и предыдущий, цепочка одинаковых символов продолжается, и нужно увеличить значение переменной cu r Len; если значение cu r Len стало больше maxLen, обновляем maxLen и запоминаем новый базовый символ в переменной c:

if s[i] == s[i-1]: # цепочка продолжается

curLen += 1     # увеличиваем длину

if curLen > maxLen: # если цепочка побила рекорд

maxLen = curLen # запоминаем её длину...

c = s [ i ]      # и образующий символ

Else:           

curLen = 1      # началась новая цепочка

если очередной символ не совпал с предыдущим, началась новая цепочка, и её длина пока равна 1 (это значение записывается в переменную cu r Len)

· получается такой цикл обработки строки:

maxLen, curLen, c = 1, 1, s[0]

for i in range(1, len(s)):

if s[i] == s[i-1]:

curLen += 1

if curLen > maxLen:

maxLen = curLen

c = s[i]

else:

curLen = 1

· проверим правильность работы алгоритма в особых случаях:

в) если вся строка состоит из одинаковых символов, значение переменной curLen постоянно увеличивается и в конце станет равно длине символьной строки; то же значение окажется и в переменной maxLen;

г) если в строке нет пар одинаковых символов, переменная curLen всегда равна 1, такое же значение будет и в переменной maxLen

Пример задания:

Р-07 (демо-2021). Текстовый файл 24.txt состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны. Для выполнения этого задания следует написать программу.

Решение:

1) считывание из файла и перебор символов аналогичен задачам Р00-Р02 (см. ниже).

2) чтобы считать длину цепочки, соответствующей условию, нам нужно будет ввести два счётчика:

curLen – длина текущей цепочки (которая сейчас обрабатывается)

maxLen – длина самой длинной на данный момент цепочки в уже обработанной части строки

3) обработка строки сводится к тому, что текущая длина цепочки увеличивается, если соседние символы, s[i-1] и s[i], различны; если это не так, сбрасываем длину текущей цепочки в 1

4) можно заметить, что эта задача очень напоминает Р-05, только тут обратное условие – нужно искать цепочку, где все соседние символы не одинаковые, а разные, поэтому и решение сводится к изменению условия (см. выделение маркером):

with open("24.txt", "r") as F:

s = F.readline()

maxLen, curLen = 1, 1

for i in range(1, len(s)):

if s[i]!= s[i-1]:

curLen += 1

if curLen > maxLen:

maxLen = curLen

else:

curLen = 1

Print(maxLen)

5) Ответ: 35.

6) программа на Паскале: