LINUX.ORG.RU

Group by longest common prefix

 , ,


0

1

Привет, а подскажите, как более правильно реализовать сабж ?
ЯП не важен.
Например:

Есть список МАК адресов (в реальной жизни он может быть порядка 10-15к):

f4:8b:32:de:b3:70
f4:8b:32:df:10:49
f4:8b:32:df:c4:10
f4:8b:32:e8:f9:86
f8:2f:a8:ac:83:e1
fc:64:ba:15:45:58
fc:64:ba:68:51:73
fc:64:ba:90:20:23


Хотелось бы на выходе получить что-то вроде такого:
f4:8b:32 = [
  f4:8b:32:de:b3:70
  f4:8b:32:df:10:49
  f4:8b:32:df:c4:10
  f4:8b:32:e8:f9:86
]

fc:64:ba = [
  fc:64:ba:15:45:58
  fc:64:ba:68:51:73
  fc:64:ba:90:20:23
]

f8:2f:a8:ac:83:e1 = [
  f8:2f:a8:ac:83:e1
]

Сейчас посматриваю на префиксное дерево, но, мне кажется, это будет дикий overhead ?
Спасибо.

★★★★★

Сейчас посматриваю на префиксное дерево, но, мне кажется, это будет дикий overhead ?

Если overhead по памяти, то есть 3-way trie с её меньшим потреблением.

xaizek ★★★★★ ()
Ответ на: комментарий от joy4eg

Я ступил. Забыл про заголовоком пока читал :)

Да, тут траи и дфс подойдут.

xpahos ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.