문제2327--Word Parts

2327: Word Parts

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 8  통과: 4
[제출] [채점기록] [묻고답하기]

문제 설명

Given a base word, original, and a compound word, compound, decide if the compound word is valid. A compound word is valid if and only if it is comprised solely of a concatenation of prefixes and/or suffixes of original. That is, if the compound word can be partitioned into N parts, such that each part is equal to either a prefix or a suffix of original, then it is valid.

 

입력 설명

First line, a number of test cases T( T <= 50)

Next line, original word.

Next line, compound word.

 

original will contain between 1 and 50 characters, inclusive.

original will consist only of uppercase letters (A-Z).

compound will contain between 1 and 50 characters, inclusive.

compound will consist only of uppercase letters (A-Z).

 

출력 설명

If the word is invalid, print -1. Otherwise, print the minimum value of N for which this is possible. The entire base word original is considered a valid prefix/suffix of itself.

 

입력 예시 Copy

3
ANTIDISESTABLISHMENTARIANISM
ANTIDISIANISMISM
ANTIDISESTABLISHMENTARIANISM
ESTABLISHMENT
ABBBAABABBBAABBABBABABBABAABBAABBBBBABBABABBABAABB
BBBAABABBBAABBABBABABBABAABBAABBBBBABBABABBABAABAA

출력 예시 Copy

3
-1
17

출처/분류