@sourav
can O(n) solution possible like this
n=1245120124587412112544735685458545512522524554745669698784552
k=362541245
1. pivot = n[i] where n[i++]=k[j++] for the first time.
2.while(j= length of k[] and i= length of n[])
{if (n[i]==k[j])
{ j++;i++;
we can reduce space complexity further more by just maintaining one
array...
a[256]={0,0,0,0,0,0,0,0,0};
As character can be non numeric... all possibility in 256 ..
s[] = input string.
for( i=0;istrlen(s);i++)
{ a[ s[i] ]++;
}
for( i=0;istrlen(s);i++)
Given n nodes, 2 players play a game by constructing a directed edge
between 2 nodes in each turn by following the 4 rules below.
1)Each player has to create 1 edge in his turn, starting from the node
reached by the previous move of the opponent.
Ex:- if player A creates an edge from node 2 to
Find longest interval:-
We are given with two arrays A and B..each of size
N...elements of array contains either 1 or 0...
we have to find such an interval (p,q)(inclusive) such that the sum of
all
the elements of A (between this interval) and sum of all elements of
B
(between this interval ) is
How to implement suffix tree in linear time.
--
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
Use Ukkonen algorithm forn an online implementation in O(n)
2010/10/31 snehal jain learner@gmail.com
How to implement suffix tree in linear time.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Design a data structure that can be used instead of an array and
avoids the high-cost (i.e. O(n)) of initializing the array. the data
structure ought to holds n items and supports the following operations
in O(1) time:
* Init - Initializes the data structure to empty.
* Set(i, x) - Sets item x at