Предложить оптимальный алгоритм для суммы расстояний первого совпадения в двух последовательностях

Question

У меня есть два списка, скажем, L1 и L2, (минимальная) сумма длин двух списков.

Например:

89 145 42 20 4 16 37 58 89

20 4 16 37 58 89

Выход: 5

89 145 42 20 4 16 37 58 89

56 678 123 65467

Выход: 0

19 82 68 100 1

100 1

Выход: 5

Спасибо

PS: Мой язык выбора - C и C ++, поэтому тэг.

Answer 1

Добавление более короткого списка в хэш (словарь) ключ = число, значение = индекс первого экземпляра в списке

Перебирайте другой список и для каждого элемента попробуйте поискать в хэше.Когда совпадение сделано, добавьте индексы вместе (значение из хэша плюс текущий индекс в списке)

Это выполняется в O (n)

boost :: unordered_map или stdex :: hash_mapиспользоваться для хэша

Answer 2

Вот алгоритм линейного времени, использующий хеш-таблицу.

Начать с элементов хеша L1 (с элементом, являющимся ключом хеша, и индексом, являющимся значением), если он еще не хеширован.

Далее, элемент foreach в L2 проверяет, был ли хэширован элемент, если да, выведите сумму индекса элемента в L2 и значение хеша (индекс того же элемента в L1) выход.

Если в хеш-таблице не найден элемент L2, выведите 0 и выйдите.

Алгоритм:

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

Answer 3

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;

Это O (1) в пространстве и худший случай O (n ^ 2) во времени. И лучший случай O (1) во времени! Этот алгоритм очень быстр для списков, имеющих совпадение в первых нескольких элементах.