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

×

all substring

can someone provide me a link aur give a hint to generate all substring of a string. i need the fastest way.

asked 12 Aug '13, 20:00

sonia22's gravatar image

0★sonia22
-1244
accept rate: 0%


If you want to emurate all substrings you cannot do better than O(n^2) because in the worst case you can have O(n^2) unique substrings and its easy to enumerate them just using two loops. But I guess just to print the substring it will take O(n) time. So, overall O(n^3).

But if you want to count the number the number of unique substrings turns out one can do much better using suffix array and lcp combination. This can be achieved in O(n) time and there are easy to code O(n lg^2 n) algos for this method.

link

answered 12 Aug '13, 20:14

arnabbcs08's gravatar image

4★arnabbcs08
99359
accept rate: 0%

actually i was solving http://www.codechef.com/problems/AMSTRING probelm..

but i modified it to taking input a integer K and a string S. now substrings are taken from S itself. lets say s1 and s2. then what should be the number of pair of string s1,s2 such that DIFF(s1,s2)<=K. any hint to solve this..

link

answered 12 Aug '13, 22:46

sonia22's gravatar image

0★sonia22
-1244
accept rate: 0%

Here is the editorial for the problem. http://discuss.codechef.com/questions/8567/amstring-editorial

link

answered 13 Aug '13, 02:50

arnabbcs08's gravatar image

4★arnabbcs08
99359
accept rate: 0%

edited 13 Aug '13, 02:51

i have read the tutorial but i am not getting how to approach for a single string.. plz help me...

link

answered 13 Aug '13, 08:59

sonia22's gravatar image

0★sonia22
-1244
accept rate: 0%

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:

×38

question asked: 12 Aug '13, 20:00

question was seen: 1,317 times

last updated: 13 Aug '13, 08:59