DIVSTR - Divisible Strings
Mathematicians have always loved generalizing mathematics to everything. They even contributed lots of optimizations and valuable formulas to Computer Science. Have you heard about String Multiplication? What do you think will happen if we write the following code in python?
print (3 * “abc”);
As you might have guessed, it prints “abcabcabc”. It is equal to print(“abc” + “abc” + “abc”);
We define string S is divisible by string T, if there is some non-negative integer k, which satisfies the equation S=k*T .
Your task is simple. Given two strings S and T. What is the minimum number of characters which should be removed from S, so S is divisible by T?
The first line of the input contains Q the number of the test cases. (1≤Q≤100)
Each test case consists of two lines.
The first line contains string S consisting of lowercase English letters. (0≤|S|≤104)
The second line contains string T consisting of lowercase English letters. (0<|T|≤104)
For each test case print a single integer, the minimum number of characters which should be removed.
Input: 4 babbaba ab dictate acid abc p q Output: 3 7 0 1
Hint: Don't think about the tag(Greedy) , this a adhoc problem with only one answer possible(so called minimum number).
easy-peasy first find all corner cases :)
Last edit: 2018-06-01 09:55:46
thank you very much @shakuniiii
Hi all! Do you know how to read a string but the length of string is 0? . Thank You