Самая страшная история

Автор задачи: Тимур Гараев, разработчик: Константин Бац

Давайте перепишем каждое слово в последовательность пар $$$\langle w_i, c_i \rangle$$$, где $$$w_i$$$ — номер слова, а $$$c_i$$$ — порядковый номер символа в слове. Это делается за один проход по всем символам в каждом слове, то есть за $$$\mathcal{O} \left(\sum\limits_{i=1}^n |s_i|\right)$$$. Для этого достаточно просто итерироваться по данной во вводе строке $$$s$$$, увеличивая $$$c_i$$$, а при встрече пробела — обнуляя $$$c_i$$$ и увеличивая $$$w_i$$$. Альтернативно можно просто считывать слова по одному, используя cin.

Далее соединим $$$n$$$ получившихся последовательностей пар. Тогда мы получим последовательность пар длины $$$\sum\limits_{i=1}^n |s_i|$$$, в которой на позиции $$$i$$$ записаны $$$w_i$$$ и $$$c_i$$$, которые равны номеру слова и позиции в слове для $$$i$$$-го символа в истории соответственно. Таким образом, ответ для каждой гипотезы — элемент полученной последовательности, который можно получить за время $$$\mathcal{O}(1)$$$.

Время работы такого решения — $$$\mathcal{O}\left(m + \sum\limits_{i=1}^n |s_i|\right)$$$.