Repeated String

Problem code: REPSTR

All submissions for this problem are available.

Given a string S (containing at most 105 lowercase English letters). You are requested to find out from continuous substrings a string having length from L to H, which appears the most times; if there are more than one answer, find the most length.

Input

There are several test cases (fifteen at most), each formed as follows:

  • The first line contains two positive integers L, H.
  • The second line contains the string S.
The input is ended with L = H = 0.

Output

For each test case, output on a line two integers which are the number of times appearing and the length of the found string, respectively.

Example

Input:
3 5
aabcbcbca
3 5
baaaababababbababbab
1 4
abcd
0 0


Output:
2 4
6 3
1 4

Explanation

Case #1: bcbc occurs twice - at position 3 and position 5 (occurrences may overlap).
Case #2: bab occurs 6 times.
Case #3: abcd occurs 1 time.
Author: anhdq
Date Added: 22-08-2011
Time Limit: 10 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

What is the range of L and

phantom11 @ 1 Oct 2011 07:43 PM
What is the range of L and H.Although conscience tells that it should be [1,s.length]....But can it be more or less??

Giving an upper bound on L

gunjanbansal @ 1 Oct 2011 11:20 PM
Giving an upper bound on L and H(if not 10^5, i.e < length of string), or better the difference between them will help.

I got stuck in reading S of

avinash1 @ 2 Oct 2011 04:37 PM
I got stuck in reading S of larger length. C++ has cin limit of 4096 & C# 256 some setting makes it 1024 :(. Tired of googling how to read large input.

@avinash read char by char to

rijin @ 2 Oct 2011 06:00 PM
@avinash read char by char to char array

What is maximum total length

jokser @ 3 Oct 2011 06:49 AM
What is maximum total length of all strings ?

is it allowed to talk on algo

gunjanbansal @ 3 Oct 2011 11:34 AM
is it allowed to talk on algo complexity ?

Can H-L be as large as 10^5 ?

gunjanbansal @ 3 Oct 2011 12:16 PM
Can H-L be as large as 10^5 ?

what is the range of l and h

bknarendra @ 3 Oct 2011 01:28 PM
what is the range of l and h

0 < L <= H < |S|

anhdq_adm @ 3 Oct 2011 02:59 PM
0 < L <= H < |S|

sorry, it should be 0 < L <=

anhdq_adm @ 3 Oct 2011 02:59 PM
sorry, it should be 0 < L <= H <= |S| exactly

is |S| = 0 allowed and if

theicebreaker @ 3 Oct 2011 06:50 PM
is |S| = 0 allowed and if yes what is its answer

i have got nzec error in

karthikccet @ 3 Oct 2011 07:32 PM
i have got nzec error in java... anyone can u help me???

i have got the same output as

karthikccet @ 3 Oct 2011 07:34 PM
i have got the same output as this problem even i tested with input file ... but when i submit it shows runtime error nzec. can any one tell me what possible input can cause exception...

exception is the nzec runtime

karthikccet @ 3 Oct 2011 07:34 PM
exception is the nzec runtime error

@karthikccet It usuallys

phantom11 @ 3 Oct 2011 07:45 PM
@karthikccet It usuallys happens if your program does not return 0...Check if your input and output are proper and are read and wriiten in System

please can u tell me clearly

karthikccet @ 3 Oct 2011 09:04 PM
please can u tell me clearly , i am begginer only ...please

You are requested to find out

theicebreaker @ 3 Oct 2011 11:06 PM
You are requested to find out from "continuous" substrings a string having length from L to H, which appears the most times; What do you exactly mean by continuous substrings; What i understand by the problem is that we have to find the most repeated substring in S where the length of the substring should be btw [L,H]

what does this runtime error

taneja_stud @ 4 Oct 2011 05:47 AM
what does this runtime error SIGSEGV mean.....

in c++

taneja_stud @ 4 Oct 2011 05:47 AM
in c++

@taneja_stud it means

migdal @ 4 Oct 2011 11:14 AM
@taneja_stud it means segmentation fault

does

theicebreaker @ 4 Oct 2011 03:43 PM
does System.out.println(maxcount + " " + maxsize); work for printing output of this problem. Or is there a problem in this somewhere. I for the life of me cant find out why my sol is giving WA. Checked every possible type of case. String size 1; string having only one type of character like all 'a's etc. strings having multiple repated substrings of all sizes.

Although i have solved this

gunjanbansal @ 4 Oct 2011 08:00 PM
Although i have solved this problem, giving bounds on L and H in the question would have helped. It makes easy to know the complexity of algorithm that will be required to write acceptable code.

i've been getting seg faults

jaskirats @ 4 Oct 2011 11:43 PM
i've been getting seg faults all day..cannot locate invalid memory access :-(

I have used just 1 nested for

phantom11 @ 5 Oct 2011 01:05 PM
I have used just 1 nested for loop for i=l to h for(j=0 to s.length()-i and it gives TLE .@AC's Have you implemented this in a better way ??

@migdal.....thnx dude

taneja_stud @ 5 Oct 2011 04:24 PM
@migdal.....thnx dude

I think number of test cases

budabudimir @ 6 Oct 2011 01:55 AM
I think number of test cases is important and it should be said. Is it 10 ?

@budabudimir Read Question

gunjanbansal @ 6 Oct 2011 09:36 PM
@budabudimir Read Question Again.

@phantom11, No complexity

gunjanbansal @ 6 Oct 2011 09:36 PM
@phantom11, No complexity Talks please.

I tried the program in Java ,

manthravadi @ 6 Oct 2011 10:45 PM
I tried the program in Java , executed it successfully...but I am getting Time Limit Exceed problem when I submit. Then, I tried it in C++ with some small changes to make it more efficient and I am still getting TLE, wondering if anyone can help me out with it :s

@matheravadi, as far as i

gunjanbansal @ 6 Oct 2011 11:03 PM
@matheravadi, as far as i have learned from FAQ and wiki, different languages have slightly different time limits. If TLE your code actually takes more time than it should.

@gunjanbansal: this problem

s1a3 @ 6 Oct 2011 11:07 PM
@gunjanbansal: this problem definitely can't b done in linear time... so what remains is n*(H-L) but it is giving me TLE... any ideas?

@s1a3 Many have solved this

gunjanbansal @ 6 Oct 2011 11:37 PM
@s1a3 Many have solved this problem

do the substrings have to be

abhishek777 @ 7 Oct 2011 04:17 PM
do the substrings have to be continuous?eg for "babccbab" ,will "bab" be the ans?

@s1a3: I think you're wrong

potaten @ 8 Oct 2011 02:32 PM
@s1a3: I think you're wrong regarding this problem being solvable in linear time...

WooHoo! Finally after 5 days

sanchit_h @ 8 Oct 2011 03:37 PM
WooHoo! Finally after 5 days of researching, AC!

how to submit the code

mahe209069 @ 3 Nov 2011 10:37 PM
how to submit the code

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions