from typing import Dict
from typing import List


def span_subwords(
        word: str,
        unk_token: str,
        vocab: Dict[str, int],
        max_input_chars_per_word: int,
    ) -> List[str]:
    """
    Tokenize a word into several subwords.

    This code is copied from Bert tokenization.py.

    Requirement: The input word should not contain whitespaces and accent tokens.

    This uses a greedy longest-match-first algorithm to perform tokenization
    using the given vocabulary.

    The default arguments in BERT are
    unk_token = '[UNK]'
    max_input_chars_per_word = 200

    E.g.
    >>> span_subwords(
            word="unaffable",
            vocab={"un": 0, "##aff": 1, "##able": 2},
            max_input_chars_per_word=200,
        )
    ["un", "##aff", "##able"]

    """

    # length of word is more than expected -> return [unk_token]
    if len(word) > max_input_chars_per_word:
        return [unk_token]

    # subword matching
    chars = list(word)
    is_bad = False
    start = 0
    sub_tokens = []
    while start < len(chars):
        end = len(chars)
        cur_substr = None
        while start < end:
            substr = "".join(chars[start: end])
            if start > 0:
                substr = "##" + substr
            if substr in vocab:
                cur_substr = substr
                break
            end -= 1
        if cur_substr is None:
            is_bad = True
            break
        sub_tokens.append(cur_substr)
        start = end

    if is_bad:
        # one of subwords is not in vocab
        return [unk_token]
    return sub_tokens