@Atul- can you explain ur approach a little more..What is A and B string wd
reference to question..for each A and B string it will take O(n) time to
make the table...ur approach is O(n)..dont think so..please explain may be
i m wrong
--
You received this message because you are subscribed to
@Carl-At each step you are calculating lcp between the text and the last
entry probably to compare ... lcp[i+1]..is it linear still
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroup
@carl-Sorry was making suffix array by naive approx in the link
http://en.wikipedia.org/wiki/Suffix_array .there are more optimized algos
for it...!! thanks
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to
I still don't understand. There's far quicker suffix array construction
algorithms than O(n^2 log n)? There's O(n) algorithms
On 20 August 2012 23:27, pankajsingh wrote:
> Thanks.carl and atul.!!.@carl-i got lgn due to string comparison sort
> while making the suffix array..:)
>
> --
> You recei
Thanks.carl and atul.!!.@carl-i got lgn due to string comparison sort while
making the suffix array..:)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this
Yeah sorry, misread the question then had a quick attempt :) I don't see
where you get the lg n from though. I didn't do any binary searches.
On 19 August 2012 22:53, pankajsingh wrote:
> @carl- got ur point..but complexity is more..suffix array takes
> o(n^2lgn)..considering string comparisons
@carl- got ur point..but complexity is more..suffix array takes
o(n^2lgn)..considering string comparisons. complexity to build...i already
have o(n^2)..want o(n)..
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send e
concatenate 2 strings adding wild character in between i.e
A="aaa"
B="aaab"
A+B ="aaa$aaab";
wild character is "$";
now create longest prefix table(partial match table) as we do in KMP
algo.
now search for max value after "$" index...in LPS table.
I guess it would work
On Sun, Aug 19, 2012
Oh, I actually read the question totally wrong. I think this idea is
linear, but it's late so I'm not sure.
1. Calculate suffix array and lcp array for the text.
2. Calculate the longest common prefix between your text and the first
entry in your suffix array and initialise a variable called tota
@Carl- I didnt got ur point completely abt Lcp array..can you demonstrate
on the below example...
Example for ababaa
answer shud be -11
suffix array wud be:-
a
aa
abaa
ababaa
baa
and Lcp array would be then
0
1
1
3
0
..correct if wrong..whats next...
--
You received this message because you
Or a suffix tree would work. Pre process it to answer Lowest common
ancestor queries.
On 19 August 2012 21:51, Carl Barton wrote:
> Just calculating the suffix array solves the problem if you do it with the
> LCP array as well. You don't need to 'use' the suffix array so to speak.
>
>
> On 19 Au
Just calculating the suffix array solves the problem if you do it with the
LCP array as well. You don't need to 'use' the suffix array so to speak.
On 19 August 2012 21:45, pankajsingh wrote:
> Is there any O(n) solution this question...I Cleared all the testcases but
> my solution is not O(n) a
soln 1 : we can take one more array B[ ] of size n. start inserting the
number from the array A[ ] into the index of array B[ ] ie number 39 from
array A[ ] will go in 39th place . finally the missing element can be
found by tracing array B[ ] .
soln 2 :Find sum of n numbers and Sum of all the n
hmm i also doubt that
but it is Strictly O(32n) not O(nlgn) where lgn <= 32 depending upon value
of n
On Fri, Jun 24, 2011 at 1:10 PM, rizwan hudda wrote:
> @sunny: Think again, your solution will take O(n*log(n)), where log(n) is
> the number of bits to represent
> the number.
>
>
> On Thu, Ju
@sunny: Think again, your solution will take O(n*log(n)), where log(n) is
the number of bits to represent
the number.
On Thu, Jun 23, 2011 at 6:51 PM, Sriganesh Krishnan <2448...@gmail.com>wrote:
> can you explain mewhat the logic is...behind the xor operation?...is it
> like inversion or enc
Sure, if only one number is missing and all the other numbers are distinct.
And we know those numbers are from 1 to n. First we xor all the numbers, we
get xor1, then we let xor1 xor with numbers from 1 to n. Since xor means 1
xor 1=0, then all the number appear in the file will null out (those bit
can you explain mewhat the logic is...behind the xor operation?...is it
like inversion or encryption?
On Thu, Jun 23, 2011 at 11:59 AM, sunny agrawal wrote:
> initially compute xor of all the values from 0 to n in a variable Temp
> so temp = 0^1^2^n
> let result is used to store the m
initially compute xor of all the values from 0 to n in a variable Temp
so temp = 0^1^2^n
let result is used to store the missing number
for each ith bit of missing number where i = 0-31 we can find it as
following
ith bit of result = (xor of all ith bits of values of array) xored with (ith
Is the array sorted?
In A[1..n], one number is missing from 0 to N. So,
A[5]={--INF, 2,1,3,0} is a valid case?
On Wed, Jun 22, 2011 at 11:51 PM, RollBack wrote:
> An array A[1...n] contains all the integers from 0 to n except for one
> number which is
> missing. In this problem, we cannot access
An array A[1...n] contains all the integers from 0 to n except for one
number which is
missing. In this problem, we cannot access an entire integer in A with
a single opera-
tion. The elements of A are represented in binary, and the only
operation we can use
to access them is “fetch the jth bit of
How to find the two numbers whose difference is minimum among the set of
numbers
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
a
21 matches
Mail list logo
