You are not logged in. Please login at www.codechef.com to post your questions!

×

Doubt in CHSTR

Can anyone please explain this ->

" From the above array we can conclude that we have 1 substring which can be choosen atleast 3 times. How? Because there are 3 entries in the above array that are greater than or equal to 1. Similarly we can deduce for 2 (2 times), 3 (2 times), 4 (1 time ) and 5(1 time). So we increment cnt[3] once, cnt[2] twice and cnt[1] twice. " ??

Specially in first sentence (from above quote) what is use of selecting 1 substring atleast 3 times ? Why would we so that ? and What will be the result of doing that ?

asked 19 Jun '15, 18:03

glow's gravatar image

3★glow
6312
accept rate: 0%


This is the algorithm with which we populate the cnt array. It means that we can find the same substring with length 1 three times. In that the case we can find the substring 'a' in three different places. Then we can find the same substring with length 2 two times (this is 'ab'), and so on.

Then we repeat the same procedure with the next suffix.

At the end we will have populated the cnt array and we can compute the answer the way it is described at the beginning.

PS. "we have 1 substring which can be choosen atleast 3 times." means the substring with length 1.

link

answered 22 Jun '15, 12:18

aragar's gravatar image

4★aragar
994
accept rate: 7%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×288
×156
×8

question asked: 19 Jun '15, 18:03

question was seen: 1,472 times

last updated: 22 Jun '15, 12:18