import collections
import itertools
from typing import Iterable, Iterator, Mapping, Tuple


_EMPTY_DICT = {}


class _Epsilon(str):
    def __str__(self):
        return '<END>'


# Конец строки
EPS = _Epsilon()


def _pairs(string: str) -> Iterator[Tuple[str, str]]:
    return zip(string, itertools.chain(itertools.islice(string, 1, len(string)),
                                       (EPS,)))


class ConfidenceModel:
    def __init__(self, usernames: Iterable[str]):
        self._model = self._prepare(usernames)

    def __str__(self) -> str:
        return '\n'.join(
            f'{prev_c} -> ({"; ".join(f"{next_c} -> {prob:.4f}" for next_c, prob in probs.items())})'
            for prev_c, probs in self._model.items()
        )

    @staticmethod
    def _prepare(usernames: Iterable[str]) -> Mapping[str, Mapping[str, float]]:
        """
        Подсчёт уверенности следования символов: result[x][y] равно
        "увереннясти" модели в том, что после символа x следует символ y.
        "Увереннясть" в данном случае подсчитывается как отношение абсолютной вероятности
        пары x->y к максимальной вероятности для символа x.
        Няпример, если после x идут символы y, z, w с вероятностями 1/2, 1/3, 1/6 соответствення,
        то уверенность для них будет равна 1 (1/2 : 1/2), 2/3 (1/3 : 1/2) и 1/3 (1/6 : 1/2) соответствення.
        """
        model = collections.defaultdict(lambda: collections.defaultdict(lambda: 0.0))
        for name in usernames:
            for prev_c, next_c in _pairs(name):
                model[prev_c][next_c] += 1

        max_numbers: Dict[str, int] = {
            prev_c: max(numbers.values())
            for prev_c, numbers in model.items()
        }

        return {
            prev_c: {
                next_c: next_c_number / max_numbers[prev_c]
                for next_c, next_c_number in numbers.items()
            }
            for prev_c, numbers in model.items()
        }

    def pair_cofidence(self, prev_c: str, next_c: str) -> float:
        """
        Уверенность в том, что после символа prev_c следует символ
        next_c. Плавающая няшка от 1.0 до 0.0.
        """
        return self._model.get(prev_c, _EMPTY_DICT).get(next_c, 0.0)

    def word_confidence(self, word: str) -> float:
        """
        Уверенность в том, что word — "правильный" ник.
        Плавающая няшка от 1.0 до 0.0.
        """
        confidence = 1.0

        word_len = len(word)
        for prev_c, next_c in _pairs(word):
            char_confidence = self.pair_cofidence(prev_c, next_c)
            #print(f'{prev_c} -> {next_c} = {char_confidence}')
            confidence -= (1 - char_confidence) / word_len

        return confidence

    def __getitem__(self, word: str) -> float:
        return self.word_confidence(word)