@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++; } i++; } if( j > length of k[] and i<= length of n[]) return the window size (pivot to i) On Mon, Oct 25, 2010 at 12:22 PM, ankur aggarwal <ankur.mast....@gmail.com>wrote: > If the order is same then the nishaanth is right.. > > let have similar problem with no constrain on order > > eg main string 12561465 > > and query string is 1 2 6 5 > then output should be "1 2 5 6" > > > On Sat, Oct 23, 2010 at 11:23 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<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > > With Regards > Ankur Aggarwal > +91-7838289304 > > Software Engineer > Slideshare > Delhi > INDIA. > > -- > 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. > -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile" -- 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.