Что спрашивают
Ввод содержит несколько строк. Нужно посчитать строки, из которых можно получить CODE удалением лишних символов без перестановки остальных. Буквы C, O, D, E должны находиться в одной строке и идти в таком порядке.
Соседство букв не требуется. Подходящая строка считается один раз, даже если слово можно выбрать несколькими способами. Строки читаются до конца ввода; первой строки с их количеством нет.
Приём решения
Для каждой строки начнём со счётчика matched = 0. Он показывает, сколько первых букв CODE уже найдено. Идём слева направо; когда символ совпадает со следующей нужной буквой, увеличиваем счётчик.
- На новой строке сбросьте число найденных букв.
- Сначала ждите C, затем O, затем D и E.
- После получения всех четырёх букв увеличьте ответ на один и закончите обработку этой строки.
Почему можно брать самую раннюю подходящую букву? Более поздняя такая же буква оставляет не больше места для продолжения. Ранний выбор не мешает собрать оставшуюся часть слова. Поэтому поиск с одним указателем достаточен, перебор комбинаций позиций не нужен.
Это поиск подпоследовательности: между нужными буквами можно удалять символы. Поиск через 'CODE' in line проверял бы непрерывную подстроку и решал другую задачу. Склеивать разные строки тоже нельзя: после границы поиск начинается заново.
Время — O(S), где S — суммарная длина строк. Код читает строки по одной, дополнительное состояние занимает O(1) памяти; весь файл хранить не требуется.
Разбор на примере
Ввод
C1O2D3E COED CCOODEE CO DE
Вывод
2
| Строка | Результат поиска | Учитываем |
|---|---|---|
| C1O2D3E | Все буквы по порядку | Да |
| COED | После D нет E | Нет |
| CCOODEE | Есть несколько способов | Один раз |
| CO | Не хватает D, E | Нет |
| DE | Нет начальных C, O | Нет |
Первая и третья строки подходят. Во второй E стоит до D, а повторной E после D нет. Последние две строки вместе содержат CODE, но объединять их нельзя. Поэтому итоговое количество подходящих строк — два.
Код на Python и C++
Основной вызов передаёт итератор стандартного ввода. break останавливает поиск в уже засчитанной строке и предотвращает обращение к букве за концом слова.
В C++ строки по одной читает цикл while (getline(cin, line)). Неверная проверка непрерывной подстроки выглядела бы там как line.find("CODE") != string::npos.
import sys
def solve(lines):
word = 'CODE'
answer = 0
for line in lines:
matched = 0
for ch in line:
if ch == word[matched]:
matched += 1
if matched == len(word):
answer += 1
break
return answer
if __name__ == '__main__':
print(solve(sys.stdin))
<iostream>
<string>
using namespace std;
int main() {
const string word = "CODE";
int answer = 0;
string line;
while (getline(cin, line)) {
size_t matched = 0;
for (char ch : line) {
if (ch == word[matched]) {
matched += 1;
if (matched == word.size()) {
answer += 1;
break;
}
}
}
}
cout << answer << endl;
}
Типичные ошибки
- Проверить только наличие четырёх букв
Порядок важен: COED не содержит CODE как подпоследовательность, хотя все нужные буквы присутствуют.
- Искать непрерывное слово
Лишние символы можно удалять. Между C, O, D, E разрешены цифры и другие буквы.
- Склеить все строки
Слово должно полностью находиться в одной строке. Сбрасывайте matched на каждой новой строке.
- Посчитать все способы выбора букв
Ответ измеряется строками. После первого успеха увеличьте ответ один раз и перейдите к следующей строке.