Обработка символьных строк
В задании 24 строку из файла в миллион символов обрабатывают программой за один проход слева направо. Для подсчёта и поиска подстрок есть встроенные count, find, split и replace. Самый длинный фрагмент с условием находят счётчиком текущей длины, разрезанием строки или списком позиций нужных символов.
Как обработать строку из файла
Строку читают из файла целиком и проходят по ней один раз: перебор всех фрагментов для миллиона символов слишком долгий.
- Чтение:
s = open('24.txt').read().strip(). Символ с номером —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. - Фрагмент без символа или с ровно символами: разрежьте строку
splitили выпишите список позиций этих символов.
Строка из файла
Строка в Python — последовательность символов. open('24.txt').read() читает весь файл в одну строку. В конце файла часто стоит невидимый перевод строки, поэтому добавляют .strip(): он убирает пробельные символы по краям. Символы нумеруются с нуля: первый — s[0], последний — s[len(s) - 1]. Срез s[i:j] — подстрока с номерами от до .
Символы сравнивают по алфавиту: 'X' < 'Y' истинно. c.isdigit() проверяет, что символ — цифра, c in 'AEIOU' — что он входит в набор. Число превращают в строку через str(n), строку цифр в число — через int(s): числа и строки.
Подсчёт вхождений
s.count(v) возвращает число вхождений подстроки v без наложения: после найденного вхождения поиск продолжается с символа за ним. Для одного символа и для подстрок, которые не могут перекрываться, этого достаточно: s.count('A'), s.count('BC').
Если вхождения могут перекрываться, как ABA в ABABA, count пропустит часть из них. Тогда проверяют каждую позицию: цикл по от 0 до len(s) - k и сравнение среза s[i:i + k] с v.
Пример
Сколько раз подстрока ABA входит в строку ABABABA?
- 1.
s.count('ABA')находит ABA с позиции 0, затем ищет с позиции 3 и находит ABA с позиции 4. Результат 2. - 2.Цикл проверяет срезы с позиций 0, 1, 2, 3, 4. ABA стоит на позициях 0, 2 и 4.
- 3.Вхождения с позиции 2 перекрываются с соседними, поэтому
countеё пропустил. Ответ — 3 вхождения.
Ответ: 3 вхождения, count даёт 2
Поиск, замена и разбиение на слова
v in s — проверка, есть ли подстрока v в строке. s.find(v) возвращает номер первого символа первого вхождения, а если вхождения нет — . s.find(v, i) ищет начиная с позиции . 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.Первое «кот» начинается с позиции 0.
- 2.С позиции 1 ищем дальше: второе «кот» начинается с позиции 12.
- 3.«пёс» в строке нет: .
- 4.
s.split()даёт 5 слов: кот, и, кит, и, кот. - 5.Замена с третьим аргументом 1 меняет только первое «кот».
Ответ: 0, 12, , 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.XYZ: длина 3. Пара ZZ нарушает условие, новый фрагмент начинается со второй Z.
- 2.ZXYXZY: длина 6. Пара YY нарушает условие, новый фрагмент начинается со второй Y.
- 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]), перебираем все .
Пример
Строка XYZXXYYZYZXYX. Найдите наибольшую длину фрагмента без Z и фрагмента, где Z встречается не больше одного раза.
- 1.
s.split('Z')даёт куски XY, XXYY, Y, XYX длиной 2, 4, 1, 3. Без Z: 4. - 2.Пары соседних кусков с одной Z: , , . Наибольшая длина 7.
Ответ: 4 и 7
Шаблон из нескольких символов: цепочка пар
Иногда фрагмент состоит из повторов шаблона, например пар «согласная + гласная». Проверяем шаблон с позиции : s[i] in 'CDF' and s[i + 1] in 'AO'. Если шаблон подошёл, счётчик пар растёт и сдвигается на длину шаблона, i += 2. Если нет, счётчик обнуляется и сдвигается на 1: следующая цепочка может начаться с соседнего символа.
В таком цикле меняется по-разному, поэтому нужен while, а не for. Ответ — число пар, а не число символов, если вопрос не говорит иначе.
Пример
Строка CADOFAAFODOCX из букв A, C, D, F, O, X; гласные — A и O. Найдите наибольшее число идущих подряд пар «согласная + гласная».
- 1.CA, DO, FA — три пары подряд. Затем A не согласная: счётчик обнуляется.
- 2.С позиции 6 стоит AF — не пара, сдвиг на 1. Затем FO, DO — две пары, затем CX — не пара.
- 3.Наибольшее число пар 3.
Ответ: 3
Ровно K вхождений: список позиций
Самый длинный фрагмент, в котором символ T встречается ровно раз, содержит соседних по порядку букв T. Выпишите номера всех T в список p и добавьте по краям и len(s): это границы строки. Обозначим через элемент списка с номером . Для соседних в списке букв T с номерами от до фрагмент начинается сразу после предыдущей T и кончается прямо перед следующей. Его длина . Наибольшую длину ищут перебором . Если вместо символа считают пары, например BC, фрагмент может захватить первую букву следующей пары и вторую букву предыдущей. Общий приём — в теме скользящее окно.
Пример задания
Открытый банк ФИПИ
Текстовый файл состоит из символов T, U, V, W, X, Y и Z.
Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ T встречается ровно 100 раз.
Для выполнения этого задания следует написать программу.
Границы фрагмента: начало и конец по правилу
Иногда у фрагмента есть правило для первого и последнего символа: запись числа без ведущих нулей, чётное число. Сначала разрежьте строку на наибольшие куски из допустимых символов: накапливайте символы в cur, а на недопустимом символе обрабатывайте кусок и начинайте новый. Затем у каждого куска отрежьте лишнее с краёв: ведущие нули — cur.lstrip('0'), нечётные цифры в конце — циклом while, пока последний символ не станет чётной цифрой. В системе с чётным основанием все разряды, кроме последнего, умножаются на степени основания, то есть на чётные числа. Поэтому чётность числа определяет последняя цифра: последние цифры.
Пример задания
Открытый банк ФИПИ
Задание выполняется с использованием прилагаемых файлов.
Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в этом файле последовательность идущих подряд символов, представляющих собой запись максимального чётного 14-ричного числа. В ответе запишите количество символов (значащих цифр в записи числа) в этой последовательности.
Примечание. Латинские буквы A, B, C и D означают цифры из алфавита 14-ричной системы счисления.
Проверьте себя
00