@nishaanth
Yes its a sub sequence problem like a case when one string is
completely inside another (non continuous). But here we need to find
the smallest window. There mey be multiple occurances of elements of
input array in larger array. Also a DP approach having O(n^2) time and
space complexity, where you use a matrix of side (length of array
1)X(length of array 2) is known to me.
I am looking for a better order solution.
Thanks for your time.
Sourav
On Oct 23, 10:53 pm, nishaanth <nishaant...@gmail.com> wrote:
> It is nothing but a common subsequence problem...isnt it ?
>
> On Wed, Oct 13, 2010 at 3:42 PM, Mridul Malpani
> <malpanimri...@gmail.com>wrote:
>
>
>
> > @ ankit agarwal, you are right. thanx man.
>
> > On Oct 13, 11:37 am, prodigy <1abhishekshu...@gmail.com> wrote:
> > > Let I,Q be input array,query array respectively.
>
> > > 1. Sort query array. O(klogk)
> > > 2. Allocate an array A of size N.
> > > 3. Fill A such that A[i]= position of Q[i] in I, -1 if not present in
> > > I. O(nlogk)
> > > 4. Allocate an array B of size k with all elements initiated to -1.
> > > 5. for(counter=0,i=0,counter<n,i++)
> > > {
> > > if(B[i]==-1)
> > > counter++;
> > > if(A[i]!=-1)
> > > B[A[i]] = i
> > > }
> > > 6. Build min-heap of B.(use an auxiliary array C to keep track of
> > > position of last occurence of an element of Q in min-heap B.)
> > > 7. for(diff=i-B[1] ; i<n; i++)
> > > if(A[i]!=-1)
> > > B[C[A[i]] = i
> > > //percolate up or down if needed
> > > diff=max(diff,i-B[1]);
>
> > > 8. print diff
>
> > > On Oct 7, 1:20 pm, RAHUL KUJUR <kujurismonu2...@gmail.com> wrote:
>
> > > > @prodigy: how is it coming O(nlogk) can u explain???
>
> > --
> > 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
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
