×

# all substring

 0 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 0★sonia22 -1●2●4●4 accept rate: 0%

 1 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. answered 12 Aug '13, 20:14 99●3●5●9 accept rate: 0%
 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.. answered 12 Aug '13, 22:46 0★sonia22 -1●2●4●4 accept rate: 0%
 0 Here is the editorial for the problem. http://discuss.codechef.com/questions/8567/amstring-editorial answered 13 Aug '13, 02:50 99●3●5●9 accept rate: 0%
 0 i have read the tutorial but i am not getting how to approach for a single string.. plz help me... answered 13 Aug '13, 08:59 0★sonia22 -1●2●4●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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