suppose n is the size of S and m is the size of T
make to pointers p1=0 and p2=0
make another array C[]={0,0,...} which c[i] counts the number
of occurrence of T[i] in S[p1],S[p1+1]...S[p2]
n1=0 is the number of nonzero elements in C so each time n1==m means that
range p1..p2 can be an answer
first increase p2 (and C[i]s if necessary) until n1==m so if p2==n and n1<m
then there is no such subsequence
now increase p1 until still n1==m
now each time try to add a new element from S (S[p2+1])
and see if we can increase p1 which means decreasing C[S[p1]] doesn't make
it 0
continue until p2==nmin(p2-p1+1) in every step will yield the result (this algo doesn't work fine if we have duplicates in T) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
