Как определить, является ли список подмножеством другого списка?

Question

Какой эффективный способ определить, является ли список подмножеством другого списка?

Пример:

is_subset(List(1,2,3,4),List(2,3))    //Returns true
is_subset(List(1,2,3,4),List(3,4,5))  //Returns false

Я в основном ищу эффективный алгоритм и не слишком беспокоюсь о том, как хранится список. Это может быть сохранено в массиве, списке ссылок или другой структуре данных.

Спасибо

РЕДАКТИРОВАТЬ: список отсортирован

Answer 1

Вы можете увидеть проблему, чтобы проверить, является ли список подмножеством другого списка, как и та же проблема, чтобы проверить, принадлежит ли подстрока к строке. Наиболее известным алгоритмом для этого является KMP (Кнут-Моррис-Пратт). Посмотрите в Википедии псевдокод или просто используйте какой-нибудь метод String.contains, доступный на языке по вашему выбору. =) * * Тысяча одна

Answer 2

Вы должны взглянуть на реализацию поиска по методу STL. Я думаю, что так будет в C ++.

http://www.sgi.com/tech/stl/search.html

Описание:

Поиск находит подпоследовательность в диапазоне [first1, last1), которая идентична [first2, last2) при сравнении элемент за элементом

Answer 3

Эффективный алгоритм использует некий конечный автомат, в котором вы сохраняете принимающие состояния в памяти (в python):

def is_subset(l1, l2):
    matches = []
    for e in l1:
        # increment
        to_check = [0] + [i+1 for i in matches]
        matches = [] # nothing matches
        for i in to_check:
            if l2[i] = e:
                if i == len(l2)-1:
                    return True
                matches.append(i)
    return False

РЕДАКТИРОВАТЬ: конечно, если список отсортирован, вам не нужен этот алгоритм, просто выполните:

def is_subset(l1, l2):
    index = 0
    for e in l1:
        if e > l2[index]:
            return False
        elif e == l2[index]:
            index += 1
        else:
            index == 0
        if index == len(l2):
            return True
    return False