Problem:

Problem D: AABABCAC

Problem

  文字列$s$,$t$が与えられる。

  最初、文字列集合$A=${$s$},$B=\phi$とする。

  このとき、次の操作をできるだけたくさん行いたい。

  
操作

  
step1

  全ての $u ∊ A$ について、以下の処理を行う。

  

    
  
$u$の全ての部分列(連続でなくてもよい)から、$t$と等しいものを任意に1つ選ぶ。選んだ部分列の$u$に対応するインデックスをそれぞれ$z_1$, $z_2$, …, $z_{|t|}$とする(ただし1 $\le$ $z_1$ $\lt$ $z_2$ $\lt$ … $\lt$ $z_{|t|}$ $\le$ $|u|$)。そのような部分列がなければ操作を終了する。
  

							      
  
選んだ部分列の文字$u_{z_1}$, $u_{z_2}$, …, $u_{z_{|t|}}$でもとの文字列を分割し、それらを$B$に追加する。
  

  例えば、$u=$"abcdcd", $t=$"ac"の場合は次の2通りの分割の方法が考えられる。

 $u$の1番目の文字と3番目の文字を選んだ場合、""と"b"と"dcd"に分割される。

 $u$の1番目の文字と5番目の文字を選んだ場合、""と"bcd"と"d"に分割される。
  
  

  
step2

  $A$を$B$に置き換え、$B$を空にする。

  操作回数を1増やす。

部分列の例

 "abac"の部分列は、
  { "" , "a" , "b" , "c" , "aa" ,"ab" , "ac" , "ba" , "bc" , "aac" , "aba" , "abc" , "bac" , "abac" }
  である。

  "a"は"abac"の1文字目、または3文字目を抜き出すことによってできた部分列である。

  "ac"は"abac"の1文字目と4文字目、または3文字目と4文字目を抜き出すことによってできた部分列である。
  

Input

入力は以下の形式で与えられる。

$s$
$t$

1行目に文字列$s$,2行目に文字列$t$が与えられる。

Constraints

入力は以下の条件を満たす。

  
1 $\le$ $|t|$ $\le$ $|s|$ $\le$ $10^5$

  
文字列$s$,$t$に含まれる文字はアルファベットの大文字または小文字

Output

操作回数の最大値を出力せよ。

Sample Input 1

AABABCAC
A

Sample Output 1

2

  1回目の操作は、$A=${ "AABABCAC" }で始まる。

  step1では、$u=$"AABABCAC"に対して、例えば4番目の文字を$t$と等しい部分列として選び、"AAB"と"BCAC"に分割し、それらを$B$に追加する。

  step2では、$A$を$B$に置き換え、$B$を空にし、操作回数は1となる。

  2回目の操作は、$A=${ "AAB" , "BCAC" }で始まる。

  step1では、$u=$"AAB"に対して、例えば1番目の文字を$t$と等しい部分列として選び、""と"AB"に分割し、それらを$B$に追加する。次に$u=$"BCAC"に対して、3番目の文字を$t$と等しい部分列として選び、"BC"と"C"に分割し、それらを$B$に追加する。

  step2では、$A$を$B$に置き換え、$B$を空にし、操作回数は2となる。

  3回目の操作は、$A=${ "" , "AB" , "BC" , "C" }で始まる。

  step1では、$u=$""に対して、$t$と等しい部分列が存在しないため、ここで操作を終了する。

  この例の場合、3回目の操作ではstep1で操作が終了したため、操作回数は2となる。

Sample Input 2

abaabbabaabaabbabbabaabbab
ab

Sample Output 2

3

Sample Input 3

AbCdEfG
aBcDeFg

Sample Output 3

0



Sample input:
AABABCAC
A


Sample output:
2

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
ti = count = 0
for i,c in enumerate(S):
    if c == T[ti]:
        ti += 1
        if ti == len(T):
            ti = 0
            count += 1

ans = tmp = 0
while tmp <= count:
    tmp += 2**ans
    ans += 1
print(ans - 1)

Submission status: Accepted

Solution code:
s = input()
t = " " + input()
line = [1]
next = 1
t_size = len(t)
flag = False
for i in s:
    if t[next] == i:
        line[0] += 1
        next = line[0]
        line += [0]
        j = 0
        while line[j] == t_size:
            line[j] = 0
            next = line[j + 1] = line[j + 1] + 1
            j += 1
        if line[-1] == 0:
            line.pop()
print(len(line) - 1)