Макс: а что с ними? Регулярку указывайте в utf-8, все входные данные перед обработкой приводите к ней же, если они уже по какой-то странной причине не в этой кодировке.
wasm: Твой вопрос звучит так: "Как на Python найти все вхождения русских слов" ответ ищет все вхождения слов с русскими символами. О предложениях никто не говорил.