Given an array of strings(Say S[]), and a big string (Say B). Now how to find shortest substring from a big string B, which contains all strings (S[] ).
Use min heap with size S.length . Each heap entry contains (start,k) where start is the starting index of Kth string in B. Heap is managed based on start value.
Initially, find the starting index of each S and put it in heap.
int range, min,max
While( heap size > 0 ){
tMin = removeMin(heap); tMax = getMax(heap); if( range > (tMax - tMin){ range = tMax - tMin; min = tMin; max = tMax; } find next starting index for the string associated with tMin, and insert it into heap.
Use min heap with size S.length .
ReplyDeleteEach heap entry contains (start,k) where start is the starting index of Kth string in B.
Heap is managed based on start value.
Initially, find the starting index of each
S and put it in heap.
int range, min,max
While( heap size > 0 ){
tMin = removeMin(heap);
tMax = getMax(heap);
if( range > (tMax - tMin){
range = tMax - tMin;
min = tMin;
max = tMax;
}
find next starting index for the string associated with tMin, and insert it into heap.
}
Note:
ReplyDeleteThe same algorithm can be used find the below problem.
Given A[1..n] and B[1..m] , find the range in A say A[l...u] which contains all the elements B[1..m].