美团 8/29 笔试题 算法第三题解法（python）

import sys
from collections import defaultdict
from bisect import bisect_left

s = sys.stdin.readline().strip()
a = sys.stdin.readline().strip()


def getIdx(s, a):
    ch2indices = defaultdict(list)
    for i, ch in enumerate(s):
        ch2indices[ch].append(i)

    for ch in a:
        if ch not in ch2indices:
            return -1

    indices = []
    continue_seq = ''
    ith = 0
    sidx = 0
    while ith < len(a):
        ch = a[ith]
        idx = bisect_left(ch2indices[ch], sidx)
        if idx != len(ch2indices[ch]):
            continue_seq += ch
            sidx = ch2indices[ch][idx] + 1
            ith += 1
        else:
            indices.append(sidx)
            continue_seq = ''
            sidx = 0

    if continue_seq:
        indices.append(sidx)
    total_idx = len(s) * (len(indices) - 1) + indices[-1] - len(a)
    return total_idx


print(getIdx(s, a))