Problem:


Score : 500 points

Problem Statement

Given are two strings s and t consisting of lowercase English letters. Determine if there exists an integer i satisfying the following condition, and find the minimum such i if it exists.

Let s' be the concatenation of 10^{100} copies of s. t is a subsequence of the string {s'}_1{s'}_2\ldots{s'}_i (the first i characters in s').

Notes

A subsequence of a string a is a string obtained by deleting zero or more characters from a and concatenating the remaining characters without changing the relative order. For example, the subsequences of contest include net, c, and contest.

Constraints

1 \leq |s| \leq 10^5

1 \leq |t| \leq 10^5

s and t consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s
t

Output

If there exists an integer i satisfying the following condition, print the minimum such i; otherwise, print -1.

Sample Input 1

contest
son

Sample Output 1

10

t = son is a subsequence of the string contestcon (the first 10 characters in s' = contestcontestcontest...), so i = 10 satisfies the condition.

On the other hand, t is not a subsequence of the string contestco (the first 9 characters in s'), so i = 9 does not satisfy the condition.

Similarly, any integer less than 9 does not satisfy the condition, either. Thus, the minimum integer i satisfying the condition is 10.

Sample Input 2

contest
programming

Sample Output 2

-1

t = programming is not a substring of s' = contestcontestcontest.... Thus, there is no integer i satisfying the condition.

Sample Input 3

contest
sentence

Sample Output 3

33

Note that the answer may not fit into a 32-bit integer type, though we cannot put such a case here.



Sample input:
contest
son


Sample output:
10

Submission status: Wrong Answer

Solution code:
import sys
from string import ascii_lowercase as a2z

input = sys.stdin.readline


def main():
    S = input().rstrip()
    T = input().rstrip()

    N = len(S)
    memo = [None] * N
    memo[-1] = {alphabet: -1 for alphabet in a2z}
    memo[-1][S[-1]] = N - 1
    for i in reversed(range(N - 1)):
        memo[i] = memo[i + 1].copy()
        memo[i][S[i]] = i

    ans = 0
    idx_S = 0
    for t in T:
        i = memo[idx_S][t]
        if i == -1:
            ans += (N - idx_S)
            idx_S = 0
            i = memo[idx_S][t]
            if i == -1:
                ans = -1
                break
            else:
                if i == N - 1:
                    idx_S = 0
                    ans += 1
                else:
                    ans += i - idx_S + 1
                    idx_S = i + 1
        else:
            if i == N - 1:
                idx_S = 0
                ans += 1
            else:
                ans += i - idx_S + 1
                idx_S = i + 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

S = input()
T = input()

ss = set(list(S))
st = set(list(T))
if not (st <= ss):
    print(-1)
    exit()
alpha = {chr(97+i): [] for i in range(26)}
for i, s in enumerate(S):
    alpha[s].append(i+1)
n = len(S)
now = 0
ans = 0
for t in T:
    if alpha[t][-1] <= now:
        ans += (n - now) + alpha[t][0]
        now = alpha[t][0]
    else:
        i = bisect_left(alpha[t], now)
        ans += alpha[t][i] - now
        now = alpha[t][i]
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

S = input()
T = input()

ss = set(list(S))
st = set(list(T))
if not (st <= ss):
    print(-1)
    exit()
alpha = {chr(97+i): [] for i in range(26)}
for i, s in enumerate(S):
    alpha[s].append(i+1)
n = len(S)
now = 0
ans = 0
for t in T:
    if alpha[t][-1] < now:
        ans += (n - now) + alpha[t][0]
        now = alpha[t][0]
    else:
        i = bisect_left(alpha[t], now)
        ans += alpha[t][i] - now
        now = alpha[t][i]
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
from bisect import bisect_left, bisect_right

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    s = S()
    t = S()

    chars = {ch: [] for ch in alphabets}

    for i, ch in enumerate(s):
        chars[ch].append(i)

    ans = 0
    last = -1
    for ch in t:
        if len(chars[ch]) == 0:
            print(-1)
            return

        idx = bisect_right(chars[ch], last) % len(chars[ch])
        ans += (chars[ch][idx] - last) % len(s)
        last = chars[ch][idx]

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    s = S()
    t = S()

    manage = defaultdict(int)
    chars = {ch: [] for ch in alphabets}

    for i, ch in enumerate(s):
        chars[ch].append(i)

    ans = 0
    last = 0
    for ch in t:
        if len(chars[ch]) == 0:
            ans = -2
            break
        ans += (chars[ch][manage[ch]] - last) % len(s)

        last = chars[ch][manage[ch]]
        manage[ch] = (manage[ch] + 1) % len(chars[ch])

    print(ans + 1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
S = input()
T = input()
al = [[] for _ in range(26)]
S += S
len_t = len(T)

for i, s in enumerate(S):
    al[ord(s)-97].append(i)

al_len = []
for i in range(26):
    al_len.append(len(al[i]))

x = 0
loop = 0
for i, t in enumerate(T):
    num = ord(t)-97
    if al[num]:
        bi = bisect.bisect_left(al[num], x)

        if i == len_t-1:
            if bi == al_len[num]:
                loop += 1
                x = al[num][0]
            else:
                x = al[num][bi]
            break

        if bi == al_len[num]:
            loop += 1
            x = al[num][0]
        else:          
            x = al[num][bi] + 1
    else:
        print(-1)
        exit()
print(x+1 + loop*len(S))

Submission status: Wrong Answer

Solution code:
import bisect
S = input()
T = input()
al = [[] for _ in range(26)]
S += S

for i, s in enumerate(S):
    al[ord(s)-97].append(i)

al_len = []
for i in range(26):
    al_len.append(len(al[i]))

x = 0
loop = 0
for t in T:
    num = ord(t)-97
    if al[num]:
        bi = bisect.bisect(al[num], x)
        if bi == al_len[num]:
            loop += 1
            x = al[num][0]
        else:
            x = al[num][bi]
    else:
        print(-1)
        exit()
print(x+1 + loop*len(S))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

s=input()
sset = set(s)
t=input()

s_loc = defaultdict(list)
for i in range(len(s)):
  s_loc[s[i]].append(i)

ok=1
count = 0
last = t[0]
for i in range(len(t)):
  if t[i] not in sset:
    print(-1)
    ok=0
    break
  else:
    j=0
    new = s_loc[t[i]][j]
    if i > 0 and new <= old:
      if len(s_loc[t[i]])==1:count += 1
      else:
        while 1:
          if j == len(s_loc[t[i]])-1:
            count += 1
            break
          if s_loc[t[i]][j+1] > old:
            new = s_loc[t[i]][j+1]
            break
          j += 1
    elif i > 0 and new > old:
      last = t[i]
    if i == 0:old = t[i]
    old = new
    
if ok==1:
  print(count * len(s) + s_loc[last][0]+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

s=input()
sset = set(s)
t=input()

s_loc = defaultdict(list)
for i in range(len(s)):
  s_loc[s[i]].append(i)

ok=1
count = 0
last = t[0]
for i in range(len(t)):
  if t[i] not in sset:
    print(-1)
    ok=0
    break
  else:
    j=0
    new = s_loc[t[i]][j]
    if i > 0 and new <= old:
      if len(s_loc[t[i]])==1:count += 1
      else:
        while 1:
          if j == len(s_loc[t[i]])-1:
            count += 1
            break
          if s_loc[t[i]][j+1] > old:
            new = s_loc[t[i]][j+1]
            break
          j += 1
    elif i > 0 and new > old:
      last = t[i]
    if i == 0:old = t[i]
    old = new
    
if ok==1:
  print(count * len(s) + s_loc[last][0]+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

s=input()
sset = set(s)
t=input()

s_loc = defaultdict(list)
for i in range(len(s)):
  s_loc[s[i]].append(i)

ok=1
count = 0
last = t[0]
for i in range(len(t)):
  if t[i] not in sset:
    print(-1)
    ok=0
    break
  else:
    new = s_loc[t[i]][0]
    if i > 0 and new <= old:
      count += 1
    elif i > 0 and new > old:
      last = t[i]
    if i == 0:old = t[i]
    old = new
    
if ok==1:
  print(count * len(s) + s_loc[last][0]+1)

Submission status: Wrong Answer

Solution code:
import bisect
ind = {}
s = input()
t = input()
for i, c in enumerate(s):
    if c in ind:
        ind[c].append(i+1)
    else:
        ind[c] = [i+1]
k = len(s)
nk = 0
if not t[0] in ind:
    print(-1)
    exit()
nw = ind[t[0]][0]
pv = nw
for i in range(1, len(t)):
    c = t[i]
    if not c in ind:
        print(-1)
        exit()
    if ind[c][-1]>pv:
        pv = ind[c][bisect.bisect_left(ind[c], pv)]
        nw = pv + nk 
    else:
        nk += k
        pv = ind[c][0]
        nw = pv + nk
print(nw)

Submission status: Wrong Answer

Solution code:
import bisect
ind = {}
s = input()
t = input()
for i, c in enumerate(s):
    if c in ind:
        ind[c].append(i+1)
    else:
        ind[c] = [i+1]
k = len(s)
nk = 0
if not t[0] in ind:
    print(-1)
    exit()
nw = ind[t[0]][0]
pv = nw
for i in range(1, len(t)):
    c = t[i]
    if not c in ind:
        print(-1)
        exit()
    if max(ind[c])>pv:
        pv = ind[c][bisect.bisect_left(ind[c], pv)]
        nw = pv + nk 
    else:
        nk += k
        pv = ind[c][0]
        nw = pv + nk
print(nw)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

s, t = input(), input()
lens, sets = len(s), set(s)

if not all(i in sets for i in t):
    print(-1)
    exit()

alp = [[] for i in range(26)]
for i, si in enumerate(s):
    alp[ord(si) - 97].append(i)

ans, cnt = 1 - lens, 0
for i in t:
    li = alp[ord(i) - 97]
    ans += lens * (cnt == 0)
    num = bisect(li, cnt)
    ans += lens * (num == len(li))
    cnt = (li[num % len(li)]) % lens
print(ans + cnt % lens)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bisect
from collections import defaultdict


s, t = input(), input()

if not all(i in s for i in t):
    print(-1)
    exit()

alp = defaultdict(list)
for i, si in enumerate(s):
    alp[si].append(i)

ans, cnt = 1 - len(s), 0
for i in t:
    ans += (cnt == 0) * len(s)
    num = bisect(alp[i], cnt)
    ans += len(s) * (num == len(alp[i]))
    cnt = alp[i][num % len(alp[i])] % len(s)
print(ans + (cnt - 1) % len(s))

Submission status: Wrong Answer

Solution code:
s, t = input(), input()

if not all(i in s for i in t):
    print(-1)
else:
    ans, cnt = 1, 0
    lens = len(s)
    for i in t:
        if i in s[cnt:]:
            cnt = (cnt + s[cnt:].index(i) + 1) % lens
        else:
            ans += len(s)
            cnt = (s.index(i) + 1) % lens
    print(ans + (cnt - 1) % lens)

Submission status: Wrong Answer

Solution code:
import bisect

def ctoi(char):
  return ord(char)-ord('a')

s=input()
l=len(s)
t=input()
if len(set(t)-set(s))!=0:
  print(-1)
  exit()
pos=[[] for _ in range(26)]
for i in range(2*l):
  pos[ctoi(s[i%l])].append(i)
index=0
loop=0
for i in range(len(t)):
  tmp=bisect.bisect_right(pos[ctoi(t[i])],index)
  next_index=pos[ctoi(t[i])][tmp]
  if next_index>=l:
    loop+=1
  index=next_index%l
print(l*loop+index+1)

Submission status: Wrong Answer

Solution code:
import bisect

def ctoi(char):
  return ord(char)-ord('a')

s=input()
l=len(s)
t=input()
if len(set(t)-set(s))!=0:
  print(-1)
  exit()
pos=[[] for _ in range(26)]
for i in range(2*l):
  pos[ctoi(s[i%l])].append(i+1)
index=0
loop=0
for i in range(len(t)):
  tmp=bisect.bisect_left(pos[ctoi(t[i])],index)
  next_index=pos[ctoi(t[i])][tmp]
  if next_index>=l:
    loop+=1
  index=next_index%l
print(l*loop+index)

Submission status: Wrong Answer

Solution code:
import bisect

def ctoi(char):
  return ord(char)-ord('a')

s=input()
l=len(s)
t=input()
if len(set(t)-set(s))!=0:
  print(-1)
  exit()
pos=[[] for _ in range(26)]
for i in range(2*l):
  pos[ctoi(s[i%l])].append(i)
index=0
loop=0
for i in range(len(t)):
  tmp=bisect.bisect_left(pos[ctoi(t[i])],index)
  next_index=pos[ctoi(t[i])][tmp]
  if next_index>=l:
    loop+=1
  index=next_index%l
print(l*loop+index+1)

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

s = sr()
t = sr()
n = len(s)
dic = {chr(ord('a')+i):[] for i in range(26)}
for i,c in enumerate(s):
    dic[c].append(i+1)
for c in t:
    if not dic[c]:
        print('-1')
        sys.exit()
ans = 0
pre = 0
for c in t:
    ind = bisect.bisect_left(dic[c],pre)
    if ind == len(dic[c]):
        ans+=(n-pre)
        pre = dic[c][0]
        ans+=pre
    else:
        ans+=(dic[c][ind]-pre)
        pre = dic[c][ind]
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

s = input()
t = input()

a = [[] for i in range(26)]
for i in range(len(s)):
    num = ord(s[i]) - 97
    a[num].append(i)

flg = True
cnt = 0
x = 0
for i in range(len(t)):
    num = ord(t[i]) - 97
    if not a[num]:
        flg = False
        break
    for j in range(len(a[num])):
        if x < a[num][j]:
            x = copy.deepcopy(a[num][j])
            break
        if j == len(a[num])-1:
            cnt += 1
            x = copy.deepcopy(a[num][0])
            break
print(cnt*len(s) + x+1) if flg else print(-1)

Submission status: Wrong Answer

Solution code:
def resolve():
    s = input()
    t = input()
    d = {}
    for i, c in enumerate(list(s)):
        d.setdefault(c, [])
        d[c].append(i)
    
    import bisect
    nloops = 0
    prev = -1
    for c in list(t):
        if c not in d:
            print(-1)
            return
        # prevより後ろにあるcのうち、最も近いものの位置
        cidx = bisect.bisect_left(d[c], prev)
        nearc = d[c][cidx] if cidx < len(d[c]) else None
        if nearc is None:
            nloops += 1
            nearc = d[c][0]
        prev = nearc
    print(nloops*len(s)+prev+1)



if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
import sys

def LS2(): return list(sys.stdin.readline().rstrip())

s = LS2()
t = LS2()

from collections import defaultdict

dict_s = defaultdict(list)

for i in range(len(s)):
    dict_s[s[i]].append(i)

d = {}
for a in dict_s.keys():
    d[a] = 0

r = 0
u = 0
for a in t:
    if len(dict_s[a]) == 0:
        print(-1)
        exit()
    else:
        left = -1
        right = len(dict_s[a])
        while left + 1 < right:
            mid = (left + right)//2
            if dict_s[a][mid] > u:
                right = mid
            else:
                left = mid
        if right == len(dict_s[a]):
            r += 1
            u = dict_s[a][0]
        else:
            u = dict_s[a][right]

print(len(s)*r+u+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
s = input()
t = input()

n = len(s)

if set(list(t)) != (set(list(s)) & set(list(t))): ans = -1
else:
    dct = {}

    for i, ss in enumerate(s):
        if ss in dct:
            dct[ss].append(i)
        else: dct[ss] = [i]
    idx = -1
    ans = 0
    for tt in t:
        m = bisect_right(dct[tt], idx)
        if m == len(dct[tt]):
            idx = dct[tt][0]
            ans += n
        else:
            idx = dct[tt][max(0,m-1)]
    ans += idx + 1

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

s = list(input())

total_s = len(s)

t = list(input())

alf=[[] for _ in range(26)]

for i in range(len(s)):
    alf[ord(s[i])-97].append(i+1)

coti_alt = 0
now_alf = 0
ans = 0

for i in range(len(t)):
    next_alf = ord(t[i])-97

    if len(alf[next_alf]) == 0:
        print(-1)
        exit()

    if 0 < i and t[i-1] == t[i]:
        now_alf += 1
        ans += 1
        if now_alf == total_s and t[i] == s[now_alf-1]:
            continue

    serch_next_alf = bisect_left(alf[next_alf], now_alf)

    if now_alf < alf[next_alf][-1]:
        ans += alf[next_alf][serch_next_alf] - now_alf
        now_alf = alf[next_alf][serch_next_alf]
    else:
        ans += total_s - now_alf + alf[next_alf][0]
        now_alf = alf[next_alf][0]
    print(ans,now_alf)

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

s = list(input())

total_s = len(s)

t = list(input())

alf=[[] for _ in range(26)]

for i in range(len(s)):
    alf[ord(s[i])-97].append(i+1)

coti_alt = 0
now_alf = 0
ans = 0

for i in range(len(t)):
    next_alf = ord(t[i])-97

    if len(alf[next_alf]) == 0:
        print(-1)
        exit()

    if 0 < i and t[i-1] == t[i]:
        now_alf += 1
        ans += 1

    serch_next_alf = bisect_left(alf[next_alf], now_alf)

    if now_alf < alf[next_alf][-1]:
        ans += alf[next_alf][serch_next_alf] - now_alf
        now_alf = alf[next_alf][serch_next_alf]
    else:
        ans += total_s - now_alf + alf[next_alf][0]
        now_alf = alf[next_alf][0]

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

s = list(input())

total_s = len(s)

t = list(input())

alf=[[] for _ in range(26)]

for i in range(len(s)):
    alf[ord(s[i])-97].append(i+1)

coti_alt = 0
now_alf = 0
ans = 0

for i in range(len(t)):
    next_alf = ord(t[i])-97

    if len(alf[next_alf]) == 0:
        print(-1)
        exit()

    serch_next_alf = bisect_left(alf[next_alf], now_alf)

    if now_alf < alf[next_alf][-1]:
        ans += alf[next_alf][serch_next_alf] - now_alf
        now_alf = alf[next_alf][serch_next_alf]
    else:
        ans += total_s - now_alf + alf[next_alf][0]
        now_alf = alf[next_alf][0]

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

s = list(input())

total_s = len(s)

t = list(input())

alf=[[] for _ in range(26)]

for i in range(len(s)):
    alf[ord(s[i])-97].append(i+1)

if len(alf[ord(t[0])-97]) > 0:
    now_alf = alf[ord(t[0])-97][0]
    ans = alf[ord(t[0])-97][0]
else:
    now_alf = 0
    ans = 0

coti_alt = 0

for i in range(1,len(t)):
    next_alf = ord(t[i])-97

    if len(alf[next_alf]) == 0:
        print(-1)
        exit()

    serch_next_alf = bisect_left(alf[next_alf], now_alf)

    if t[i-1] == t[i]:
        coti_alt += 1
    else:
        coti_alt = 0

    if serch_next_alf + coti_alt < len(alf[next_alf]) and now_alf < alf[next_alf][serch_next_alf + coti_alt]:
        ans += alf[next_alf][serch_next_alf + coti_alt] - now_alf
        now_alf = alf[next_alf][serch_next_alf + coti_alt]
    else:
        ans += total_s - now_alf + alf[next_alf][0]
        now_alf = alf[next_alf][0]
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

s = list(input())

total_s = len(s)

t = list(input())


for i in range(len(t)):
    if t[i] not in s:
        print(-1)
        exit()

alf=[[] for _ in range(26)]

for i in range(len(s)):
    alf[ord(s[i])-97].append(i+1)

now_alf = alf[ord(t[0])-97][0]

ans = alf[ord(t[0])-97][0]

coti_alt = 0

for i in range(1,len(t)):
    next_alf = ord(t[i])-97
    serch_next_alf = bisect_left(alf[next_alf], now_alf)

    if t[i-1] == t[i]:
        coti_alt += 1
    else:
        coti_alt = 0

    if serch_next_alf + coti_alt < len(alf[next_alf]) and now_alf < alf[next_alf][serch_next_alf + coti_alt]:
        ans += alf[next_alf][serch_next_alf + coti_alt] - now_alf
        now_alf = alf[next_alf][serch_next_alf + coti_alt]
    else:
        ans += total_s - now_alf + alf[next_alf][0]
        now_alf = alf[next_alf][0]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_right

s,t=input(),input()
m=len(s)

if set(s)&set(t)!=set(t):print(-1);exit()

dict=defaultdict(list)
for i,j in enumerate(s):
    dict[j] +=[i+1]

ans,index=0,0
for i in t:
    point=bisect_right(dict[i],index)
    if point==len(dict[i]):num=dict[i][0]
    else:num=dict[i][point]

    if index>num:
        ans +=m
    index=num

print(ans+index)

Submission status: Wrong Answer

Solution code:
s,t=input(),input()
m=len(s)

A={chr(i):[] for i in range(97,97+26)}
for i,j in enumerate(s):
    A[j] +=[i+1]

ans,index=0,0
B={chr(i):0 for i in range(97,97+26)}
C={chr(i):len(A[chr(i)]) for i in range(97,97+26)}

for i in t:
    if len(A[i])==0:print(-1);exit()
    if index>=A[i][B[i]]:
        index=A[i][B[i]]
        ans +=m
        for j in range(26):
            B[chr(97+j)]=0
        if B[i]+1<C[i]:B[i] +=1
    else:
        index=A[i][B[i]]
        if B[i]+1<C[i]:B[i] +=1

print(ans+index)

Submission status: Wrong Answer

Solution code:
s,t=input(),input()
m=len(s)

A={chr(i):[] for i in range(97,97+26)}
for i,j in enumerate(s):
    A[j] +=[i+1]

ans,index=0,0
B={chr(i):0 for i in range(97,97+26)}
C={chr(i):len(A[chr(i)]) for i in range(97,97+26)}
for i in t:
    if len(A[i])==0:print(-1);exit()
    if index>A[i][B[i]]:
        index=A[i][B[i]]
        ans +=m
        for j in range(26):
            B[chr(97+j)]=0
        if B[i]+1<C[i]:B[i] +=1
    else:
        index=A[i][B[i]]
        if B[i]+1<C[i]:B[i] +=1

print(ans+index)

Submission status: Wrong Answer

Solution code:
s,t=input(),input()
m=len(s)

A={chr(i):[] for i in range(97,97+26)}
for i,j in enumerate(s):
    A[j] +=[i+1]

ans,index=0,0
B={chr(i):0 for i in range(97,97+26)}
C={chr(i):len(A[chr(i)]) for i in range(97,97+26)}
for i in t:
    if len(A[i])==0:print(-1);exit()
    if index>A[i][B[i]]:
        index=A[i][B[i]]
        ans +=m
        for j in range(26):
            B[chr(97+j)]=0
    else:
        index=A[i][B[i]]
        if B[i]+1<C[i]:B[i] +=1

print(ans+index)

Submission status: Wrong Answer

Solution code:
s,t=input(),input()
m=len(s)

A={chr(i):[] for i in range(97,97+26)}
for i,j in enumerate(s):
    A[j] +=[i+1]

ans,index=0,0
B={chr(i):0 for i in range(97,97+26)}
C={chr(i):len(A[chr(i)]) for i in range(97,97+26)}
for i in t:
    if len(A[i])==0:print(-1);exit()
    if index>A[i][B[i]]:
        index=A[i][B[i]]
        ans +=m
        for j in range(26):
            B[chr(j)]=0
    else:
        index=A[i][B[i]]
        if B[i]+1<C[i]:B[i] +=1

print(ans+index)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_e

from collections import defaultdict

S = input()
T = input()

# Tの文字はSに出ていないといけない
for ch in T:
    if ch not in S:
        print("-1")
        exit()

# Sの中での位置
iS = defaultdict(list)
for (idx, ch) in enumerate(S):
    iS[ch].append(idx)

# Tのindex
i = 0
iter_count = 0
total = 0
while i < len(T):
    Ti = T[i]
    # print(i, Ti, iS[Ti])
    flag = False
    while True:
        for iss in iS[Ti]:
            if iss + len(S) * iter_count >= total:
                total = iss + (len(S) * iter_count)
                i += 1
                # print(total, i)
                flag = True
        if flag:
            break
        iter_count += 1
print(total + 1)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
ds={}
for i in range(len(s)):
  if s[i] in ds:
    ds[s[i]].append(i+1)
  else:
    ds[s[i]]=[i+1]
n=len(s)
now=0 # mod n
ans=0
from bisect import bisect_left
for ti in t:
  if ti not in ds:
    print(-1)
    exit()
  tmp=bisect_left(ds[ti],now)
  if tmp==len(ds[ti]):
    get=n+ds[ti][0]
  else:
    get=ds[ti][tmp]
  ans+=get-now
  #print(get,now)
  now=(get)%n
print(ans)
#print(ds)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left

s = input()
t = input()

indices = defaultdict(list)
for i, v in enumerate(s):
    indices[v].append(i)

cnt = 0
cur = -1
mod = len(s)
for v in t:
    if v not in indices:
        print(-1)
        exit()

    i = bisect_left(indices[v], cur)
    j = indices[v][min(len(indices[v]) - 1, i)]

    if cur >= j:
        cnt += 1
    cur = j

print(cnt * mod + cur + 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_right

s = input()
t = input()

indices = defaultdict(list)
for i, v in enumerate(s):
    indices[v].append(i)

cnt = 0
cur = -1
mod = len(s)
for v in t:
    if v not in indices:
        print(-1)
        exit()

    i = bisect_right(indices[v], cur)
    j = indices[v][min(len(indices[v]) - 1, i)]

    if cur >= j:
        cnt += 1
    cur = j

print(cnt * mod + cur + 1)

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    T = input()
    N = len(S)

    def check(S, T):
        b = {s for s in S}
        for t in T:
            if t not in b:
                return True  # -1
        return False

    def is_ok(mid, now, ans):
        if ans <= now[mid]:
            return True
        else:
            return False

    def binary_search_meguru(now, ans):
        ng = -1
        ok = len(now)-1
        while abs(ok - ng) > 1:
            mid = ng + (ok - ng) // 2
            if is_ok(mid, now, ans):
                ok = mid
            else:
                ng = mid
        return now[ok]

    if check(S, T):
        return print(-1)

    from string import ascii_lowercase

    dic = {a: [] for a in ascii_lowercase}
    for i, s in enumerate(S):
        dic[s].append(i)
    ans = 0
    cycle = 0
    for t in T:
        now = dic[t]
        if now[-1] < ans+1:
            cycle += 1
            ans = 0
        idx = binary_search_meguru(now, ans+1)
        ans = idx
    print(ans + N*cycle + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    T = input()
    N = len(S)

    def check(S, T):
        b = {s for s in S}
        for t in T:
            if t not in b:
                return True  # -1
        return False

    def is_ok(mid, now, ans):
        if ans < now[mid]:
            return True
        else:
            return False

    def binary_search_meguru(now, ans):
        ng = -1
        ok = len(now)-1
        while abs(ok - ng) > 1:
            mid = ng + (ok - ng) // 2
            if is_ok(mid, now, ans):
                ok = mid
            else:
                ng = mid
        return now[ok]

    if check(S, T):
        return print(-1)

    from string import ascii_lowercase

    dic = {a: [] for a in ascii_lowercase}
    for i, s in enumerate(S):
        dic[s].append(i)
    ans = 0
    cycle = 0
    for t in T:
        now = dic[t]
        if now[-1] <= ans:
            cycle += 1
            ans = 0
        idx = binary_search_meguru(now, ans)
        ans = idx
    print(ans + N*cycle + 1)


if __name__ == '__main__':
    main()