import re

WORD = re.compile(r'(?:[^\W_]|[̀-ͯ᪰-᫿᷀-᷿⃐-⃿︠-︯])+')
PARTICLES = {'van', 'von', 'der', 'den', 'de', 'la', 'le', 'du', 'da', 'dos', 'di', 'del', 'al', 'el', 'bin', 'bint', 'ibn', 'ap', 'ab', 'mac', 'st'}
JOIN = set("-'’‘`.·‐‑–")


def char_scores(text, offsets, probs):
    cp = [0.0] * len(text)
    for (a, b), p in zip(offsets, probs):
        for i in range(a, b):
            if p > cp[i]:
                cp[i] = p
    return cp


def decode(text, offsets, probs, tau):
    n = len(text)
    cp = char_scores(text, offsets, probs)
    mask = bytearray(n)
    for m in WORD.finditer(text):
        a, b = m.span()
        if max(cp[a:b]) >= tau:
            mask[a:b] = b'\x01' * (b - a)
    word = bytes(mask)
    for i, ch in enumerate(text):
        if word[i] or ch.isspace():
            continue
        if cp[i] >= tau:
            mask[i] = 1
        elif ch in JOIN and 0 < i < n - 1 and word[i - 1] and word[i + 1]:
            mask[i] = 1
        elif ch == '.' and i >= 1 and word[i - 1] and text[i - 1].isupper() and (i < 2 or not text[i - 2].isalnum()):
            j = i + 1
            while j < n and text[j] in ' \t':
                j += 1
            if j < n and word[j]:
                mask[i] = 1
    spans, i = [], 0
    while i < n:
        if not mask[i]:
            i += 1
            continue
        j = i
        while j < n and mask[j]:
            j += 1
        if any(word[k] for k in range(i, j)):
            spans.append([i, j])
        i = j
    merged = []
    for a, b in spans:
        if merged and not text[merged[-1][1]:a].strip(' \t'):
            merged[-1][1] = b
        else:
            merged.append([a, b])
    return merged


def initials_of(name):
    words = [w for w in re.findall(r"[^\W\d_]+", name) if w.casefold() not in PARTICLES]
    return ''.join(w[0] for w in words).upper() if len(words) >= 2 else None


def established_initials(text, spans, cp, seed=.9):
    from_names = {initials_of(text[a:b]) for a, b in spans if ' ' in text[a:b]} - {None}
    return {text[a:b] for a, b in spans
            if re.fullmatch(r'[A-Z]{2,4}', text[a:b]) and max(cp[a:b]) >= seed and text[a:b] in from_names}


def with_initials(text, spans, cp):
    found = established_initials(text, spans, cp)
    if not found:
        return spans
    covered = bytearray(len(text))
    for a, b in spans:
        covered[a:b] = b'\x01' * (b - a)
    out = [list(x) for x in spans]
    for tok in found:
        for m in re.finditer(r'(?<![\w.&/\-])' + tok + r'(?![\w.&/\-])', text):
            a, b = m.span()
            if any(covered[a:b]):
                continue
            start = text.rfind('\n', 0, a) + 1
            end = text.find('\n', b)
            line = text[start:a] + text[b:end if end >= 0 else len(text)]
            letters = [c for c in line if c.isalpha()]
            if letters and all(c.isupper() for c in letters):
                continue
            out.append([a, b])
    out.sort()
    return out


def spans_for(text, offsets, probs, tau):
    spans = decode(text, offsets, probs, tau)
    return with_initials(text, spans, char_scores(text, offsets, probs))