Submission #51593193

---

Source Code Expand

import bisect

n = int(input())

s = input().strip()
t = input().strip()

a = {}
for i in range(len(s)):
    if s[i] not in a:
        a[s[i]] = []
    a[s[i]].append(i)

def check(k):
    global n
    if k == 0:
        return True
    x, y = 0, 0
    for i in range(len(t)):
        if t[i] not in a:
            return False
        j = bisect.bisect_left(a[t[i]], y)
        # print(i, t[i], j, a[t[i]], x, y)
        if len(a[t[i]]) - j > k:
            y = a[t[i]][j + k-1]+1
        else:
            tmp = k - (len(a[t[i]]) - j)
            x += 1
            y = 0
            x += tmp // len(a[t[i]])
            tmp %= len(a[t[i]])
            if tmp == 0:
                x -= 1
                y = a[t[i]][-1]+1
            else:
                y = a[t[i]][tmp - 1]+1
        if x > n:
            return False
    return x < n

l, r = 0, len(s)*n//len(t)+1
while l != r:
    mid = (l + r + 1)//2
    if check(mid):
        l = mid
    else:
        r = mid - 1

print(l)

Submission Info

Judge Result