|
W ramach naszej witryny stosujemy pliki cookies w celu świadczenia Państwu usług na najwyższym poziomie, w tym w sposób dostosowany
do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Państwa
urządzeniu końcowym. Możecie Państwo dokonać w każdym czasie zmiany ustawień dotyczących cookies w ustawieniach swojej przeglądarki.
|
|
|
|
|
SPOJ Problem Set (classical)
8758. Cover the string
Problem code: MAIN8_E
|
Given two strins A and B. You have to find the length of the smallest substring of A, such that B is the subsequence of this substing.
Formally speaking
you have to find the lenght of smallest possible string S such that
S is the substring of A
B is the subsequence S
Note: Subsequence of an string S is obtained by deletnig some (possibly none) of the characters from it. for example "ah" is the subsequecne of "aohol"
Given two strins A and B. You have to find the length of the smallest substring of A, such that B is the subsequence of this substing.
Formally speaking
you have to find the lenght of smallest possible string S such that
S is the substring of A
B is the subsequence S
Note: Subsequence of an string S is obtained by deletnig some (possibly none) of the characters from it. for example "ah" is the subsequecne of "aohol"
Input
First line contains T, the number of test cases. Then T test cases follow, 2 lines for each test case, 1st contains A and 2nd contain B.
|A|<=20000, |B|<=100
Output
For each test case print the answer in a new line. if no such substring exists print -1 instead.
Example
Input:
2
aaddddcckhssdd
acs
ghkkhllhjkhthkjjht
hh
Output:
10
3
|
|
|
|
RSS