SUBS - String it out
Given B[1-m], a string of characters from some alphabets, B^i is defined as string with the characters of B each repeating i times. For example, (abbacc)^3 = aaabbbbbbaaacccccc. Also, B^0 is the empty string.
Given strings X, Y made up of characters from 'a' - 'z' find the maximum value of M such that X^M is a subsequence of Y.
Input
- The first line of the input contains a positive integer t <= 20, denoting the no. of test cases.
- The following 2t lines contain the value of X and Y for the cases.
- The description of the test cases follow one after the other.
- Line 2k contains the value of X for case k; (1 <= k <= t)
- Line 2k+1 contains the value of Y for case k; (1 <= k <= t).
- The no. of characters in X , Y will be <= 500010.
Output
The output must contain t lines, each line corresponding to a test case. The value on the kth line should be the value of M for the kth pair of X and Y.
Example
Input:
3
abc
aabbcc
abc
bbccc
abcdef
abc
Output:
2
0
0
hide comments
maxine:
2021-07-23 11:48:50
How abc is subsequence of aaabbzbccc? |
|
spathak:
2021-03-08 21:33:55
AC in 1st go lol so easy!! :-) |
|
xoker:
2020-04-17 23:14:26
Can someone tell me in first test case string (X)^0 ,( X)^1 and (X)^2 is also sub sequence of string Y? |
|
coolio_1:
2020-03-12 15:44:02
AC in 1 go! |
|
wingman__7:
2020-01-08 12:31:25
I really don't know how to solve it using binary search... I used hash map to get AC |
|
mujahid_3732:
2019-05-21 20:59:08
Easier one..
|
|
k0x3r:
2018-05-04 09:31:40
Though you get AC without binary search also, really appreciate beauty of problem. |
|
Abhinav Gupta:
2017-09-09 08:25:16
Getting TLE even after applying binary search. |
|
me_milan_11:
2017-08-24 20:51:56
AC in first attempt.. :D good question |
|
baadshah_:
2016-07-06 14:23:22
AC in 1st Go!!
|
Added by: | Kashyap KBR |
Date: | 2005-12-12 |
Time limit: | 4.823s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS PERL6 VB.NET |