Задание 12
тема 4 из 4

Обработка символьных строк

В задании 24 строку из файла в миллион символов обрабатывают программой за один проход слева направо. Для подсчёта и поиска подстрок есть встроенные count, find, split и replace. Самый длинный фрагмент с условием находят счётчиком текущей длины, разрезанием строки или списком позиций нужных символов.

Главная тема в задании24Реже в задании12На карте навыков

Как обработать строку из файла

Строку читают из файла целиком и проходят по ней один раз: перебор всех фрагментов для миллиона символов слишком долгий.

  • Чтение: s = open('24.txt').read().strip(). Символ с номером ii — s[i], нумерация с нуля, длина — len(s).
  • Подсчёт: s.count(v) считает вхождения без наложения. Вхождения с наложением считают циклом по срезам s[i:i + k].
  • Поиск: v in s, s.find(v); замена — s.replace(v, w); слова по пробелам — s.split().
  • Самый длинный фрагмент с условием на соседей: счётчик cur растёт, пока условие выполняется, и сбрасывается в 1; максимум хранится в mx.
  • Фрагмент без символа или с ровно KK символами: разрежьте строку split или выпишите список позиций этих символов.

Строка из файла

Строка в Python — последовательность символов. open('24.txt').read() читает весь файл в одну строку. В конце файла часто стоит невидимый перевод строки, поэтому добавляют .strip(): он убирает пробельные символы по краям. Символы нумеруются с нуля: первый — s[0], последний — s[len(s) - 1]. Срез s[i:j] — подстрока с номерами от ii до j−1j - 1.

Символы сравнивают по алфавиту: 'X' < 'Y' истинно. c.isdigit() проверяет, что символ — цифра, c in 'AEIOU' — что он входит в набор. Число превращают в строку через str(n), строку цифр в число — через int(s): числа и строки.

Подсчёт вхождений

s.count(v) возвращает число вхождений подстроки v без наложения: после найденного вхождения поиск продолжается с символа за ним. Для одного символа и для подстрок, которые не могут перекрываться, этого достаточно: s.count('A'), s.count('BC').

Если вхождения могут перекрываться, как ABA в ABABA, count пропустит часть из них. Тогда проверяют каждую позицию: цикл по ii от 0 до len(s) - k и сравнение среза s[i:i + k] с v.

Пример

Сколько раз подстрока ABA входит в строку ABABABA?

  1. 1.s.count('ABA') находит ABA с позиции 0, затем ищет с позиции 3 и находит ABA с позиции 4. Результат 2.
  2. 2.Цикл проверяет срезы с позиций 0, 1, 2, 3, 4. ABA стоит на позициях 0, 2 и 4.
  3. 3.Вхождения с позиции 2 перекрываются с соседними, поэтому count её пропустил. Ответ — 3 вхождения.

Ответ: 3 вхождения, count даёт 2

Поиск, замена и разбиение на слова

v in s — проверка, есть ли подстрока v в строке. s.find(v) возвращает номер первого символа первого вхождения, а если вхождения нет — −1-1. s.find(v, i) ищет начиная с позиции ii. s.replace(v, w) возвращает новую строку, в которой все вхождения v заменены на w; s.replace(v, w, 1) меняет только первое. Сама строка s не меняется, результат присваивают: s = s.replace(v, w). На этих командах работает исполнитель Редактор.

s.split() разбивает строку на слова по пробельным символам: несколько пробелов подряд считаются одним разделителем. s.split('Z') режет строку по символу Z, и между двумя Z подряд получается пустая строка.

Пример

Строка s равна «кот и кит и кот». Найдите s.find('кот'), s.find('кот', 1), s.find('пёс'), число слов и результат s.replace('кот', 'пёс', 1).

  1. 1.Первое «кот» начинается с позиции 0.
  2. 2.С позиции 1 ищем дальше: второе «кот» начинается с позиции 12.
  3. 3.«пёс» в строке нет: −1-1.
  4. 4.s.split() даёт 5 слов: кот, и, кит, и, кот.
  5. 5.Замена с третьим аргументом 1 меняет только первое «кот».

Ответ: 0, 12, −1-1, 5 слов, «пёс и кит и кот»

Самый длинный фрагмент: счётчик текущей длины

Если условие касается каждой пары соседних символов, фрагмент обрывается там, где пара условие нарушает. Проходим строку один раз. cur — длина фрагмента, который заканчивается на текущем символе, mx — наибольшая длина. Если пара s[i - 1], s[i] подходит, cur += 1, иначе новый фрагмент начинается с s[i]: cur = 1. После каждого шага mx = max(mx, cur).

Меняется только условие на пару. Соседние символы различны: s[i] != s[i - 1]. Нет двух P подряд: not (s[i] == 'P' and s[i - 1] == 'P'). Буквы и цифры чередуются: s[i].isdigit() != s[i - 1].isdigit(). Символы идут в обратном алфавитном порядке с повторами: s[i] <= s[i - 1].

Пример

Найдите наибольшую длину фрагмента строки XYZZXYXZYYX, в котором каждые два соседних символа различны.

  1. 1.XYZ: длина 3. Пара ZZ нарушает условие, новый фрагмент начинается со второй Z.
  2. 2.ZXYXZY: длина 6. Пара YY нарушает условие, новый фрагмент начинается со второй Y.
  3. 3.YX: длина 2. Наибольшая длина 6.

Ответ: 6

Фрагмент без символа: разрежьте строку

Самый длинный фрагмент, в котором нет символа Z, лежит между двумя соседними Z. parts = s.split('Z') даёт все такие куски, ответ — max(len(p) for p in parts).

Если Z может встретиться не больше одного раза, фрагмент — это один кусок или два соседних куска вместе с Z между ними. Его длина len(parts[i]) + 1 + len(parts[i + 1]), перебираем все ii.

Пример

Строка XYZXXYYZYZXYX. Найдите наибольшую длину фрагмента без Z и фрагмента, где Z встречается не больше одного раза.

  1. 1.s.split('Z') даёт куски XY, XXYY, Y, XYX длиной 2, 4, 1, 3. Без Z: 4.
  2. 2.Пары соседних кусков с одной Z: 2+1+4=72 + 1 + 4 = 7, 4+1+1=64 + 1 + 1 = 6, 1+1+3=51 + 1 + 3 = 5. Наибольшая длина 7.

Ответ: 4 и 7

Шаблон из нескольких символов: цепочка пар

Иногда фрагмент состоит из повторов шаблона, например пар «согласная + гласная». Проверяем шаблон с позиции ii: s[i] in 'CDF' and s[i + 1] in 'AO'. Если шаблон подошёл, счётчик пар растёт и ii сдвигается на длину шаблона, i += 2. Если нет, счётчик обнуляется и ii сдвигается на 1: следующая цепочка может начаться с соседнего символа.

В таком цикле ii меняется по-разному, поэтому нужен while, а не for. Ответ — число пар, а не число символов, если вопрос не говорит иначе.

Пример

Строка CADOFAAFODOCX из букв A, C, D, F, O, X; гласные — A и O. Найдите наибольшее число идущих подряд пар «согласная + гласная».

  1. 1.CA, DO, FA — три пары подряд. Затем A не согласная: счётчик обнуляется.
  2. 2.С позиции 6 стоит AF — не пара, сдвиг на 1. Затем FO, DO — две пары, затем CX — не пара.
  3. 3.Наибольшее число пар 3.

Ответ: 3

Ровно K вхождений: список позиций

Самый длинный фрагмент, в котором символ T встречается ровно KK раз, содержит KK соседних по порядку букв T. Выпишите номера всех T в список p и добавьте по краям −1-1 и len(s): это границы строки. Обозначим через pjp_j элемент списка с номером jj. Для KK соседних в списке букв T с номерами от pj+1p_{j+1} до pj+Kp_{j+K} фрагмент начинается сразу после предыдущей T и кончается прямо перед следующей. Его длина pj+K+1−pj−1p_{j+K+1} - p_j - 1. Наибольшую длину ищут перебором jj. Если вместо символа считают пары, например BC, фрагмент может захватить первую букву следующей пары и вторую букву предыдущей. Общий приём — в теме скользящее окно.

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

Открытый банк ФИПИ

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

29920_24.txt

Границы фрагмента: начало и конец по правилу

Иногда у фрагмента есть правило для первого и последнего символа: запись числа без ведущих нулей, чётное число. Сначала разрежьте строку на наибольшие куски из допустимых символов: накапливайте символы в cur, а на недопустимом символе обрабатывайте кусок и начинайте новый. Затем у каждого куска отрежьте лишнее с краёв: ведущие нули — cur.lstrip('0'), нечётные цифры в конце — циклом while, пока последний символ не станет чётной цифрой. В системе с чётным основанием все разряды, кроме последнего, умножаются на степени основания, то есть на чётные числа. Поэтому чётность числа определяет последняя цифра: последние цифры.

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

Открытый банк ФИПИ

Задание выполняется с использованием прилагаемых файлов.

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в этом файле последовательность идущих подряд символов, представляющих собой запись максимального чётного 14-ричного числа. В ответе запишите количество символов (значащих цифр в записи числа) в этой последовательности.

Примечание. Латинские буквы A, B, C и D означают цифры из алфавита 14-ричной системы счисления.

1_24.txt

Проверьте себя

00

Потренируйте навык

Все задания на этот навык

Решать