Suggest an optimal algorithm for the sum of distances of the first match in two seqence

I have two list say L1 and L2, (minimum) sum of the lengths of the two lists.

For Example:

89 145 42 20 4 16 37 58 89

20 4 16 37 58 89

Output : 5

89 145 42 20 4 16 37 58 89

56 678 123 65467

开发者_StackOverflow中文版

Output : 0

19 82 68 100 1

100 1

Output : 5

Thanks,

PS: My language of choice is C and C++ hence the tag.

---

Add shorter list to hash (dictionary) key = number, value = index of first instance in list

Iterate through the other list and for each element try a lookup in the hash. When a match is made, add the indices together (value from hash plus current index in the list)

This runs in O(n)

boost::unordered_map or stdex::hash_map could be used for the hash

---

Here is a linear time algorithm using a hash table.

To start with hash elements of L1 (with element being the hash key and index being the value) if it is not already hashed.

Next, foreach element in L2 see if the element has been hashed, if yes print the sum of the index of the element in L2 and the hash value ( index of the same element in L1) and exit.

If no element of L2 is found in the hash table, print 0 and exit.

Algorithm:

foreach ele N in L1 at position pos
  if N not in hash
    hash[N] = pos
  end-if
end-foreach

foreach ele N in L2 at position pos
  if N in hash
    print pos + hash[N]
    exit
  end-if
end-foreach

print 0

---

for (int sum = 0; sum < a.length + b.length - 1; sum++)
  for (int i = 0; i < a.length && i <= sum; i++)
    if(a[i] == b[sum-i])
      return sum;
return -1;

This is O(1) in space and worst case O(n^2) in time. And best case O(1) in time! This algorithm is very quick for lists having a match in the first few elements.