All submissions for this problem are available.
A string X is a multiple of string Y if X consists of one or more copies of Y concatenated together. For e.g. 'abab' and 'ab' are multiples of 'ab'. Crazy Girl is interested in some specific properties of strings and needs to find multiples of a smaller string in a bigger string, but it is getting too cumbersome to do for large texts. Given two strings B and A, she wants to find all the substrings of string A which are multiples of string B and cannot be extended further to the left or right and are of maximal length. Help her by writing a program to automate the task. Output the location of the multiples of string B in the form of pairs (a, b) where a denotes the starting position of the multiple in string A (1 - based) and b denotes the number of times string B is repeated in the multiple.
The first line contains the string A and the second line contains the string B.
Output the required pairs (a, b) in decreasing order of a and output -1 if string B is not a substring of string A.
1 <= |A| <= 10^6
1 <= |B| <= |A|
The strings A and B consist only of lowercase letters 'a' - 'z'
aaba Output: 4 2
The pairs (8, 1) and (4, 1) are not reported because they can be extended further to the left and right respectively to form a multiple with two copies of string B.
|Tags||apoorv_j, cranium2014, medium-hard|
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.