Problem1039--重复子序列问题

1039: 重复子序列问题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 687  Solved: 250
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有两个字符串A和B,请你求出字符串A最少重复几次才能使得B是A的子序列。  

我们称X是Y的子序列当且仅当可以从Y中删除若干个字符得到X。

例如对于A="abb", B="bbaa",则A重复3次之后得到"abbabbabb",此时B="bbaa"是"abbabbabb"的子序列。

注意,原始串A即算作重复一次。

Input

多组数据。

第一行包含一个字符串A。  

第二行包含一个字符串B。  

A和B都只包含小写字母。

对于30%的数据,1 <= |A|, |B| <= 100

对于90%的数据,1 <= |A|, |B| <= 1000

对于100%的数据,1 <= |A|, |B| <= 100000

Output

一个整数代表答案。如果无论重复多少次都达不到,输出-1。

Sample Input

abb  
bbaa

Sample Output

3

HINT

不管做不做得出,思考的过程很重要~

Source/Category