E - Joint Two Strings https://atcoder.jp/contests/abc324/tasks/abc324_e

abc324_e.py

import bisect


def get_match_length(s, t):
    i = 0
    for c in s:
        if i < len(t) and t[i] == c:
            i += 1
    return i


N, T = input().split()
N = int(N)
S = [input() for _ in range(N)]
# 前方からのマッチ数
A = [get_match_length(s, T) for s in S]
T_rev = T[::-1]
# 後方からのマッチ数
B = [get_match_length(s[::-1], T_rev) for s in S]
B.sort()

ans = 0
for i in range(N):
    target = len(T) - A[i]      # A[i] + B[j] >= len(T)となるようなidxを二分探索で探す。
    j = bisect.bisect_left(B, target)
    ans += N - j
print(ans)