Структура данных для эффективной подстроки в приложении телефонной книги

Question

Я хочу сохранить контакты в телефонной книге, , и я хочу, чтобы пользователь выполнил поиск только части имени.

, например: Телефонная книга содержит:

Tom, John, Eve, Barbi ,Johnathon. 

Теперь поиск пользователей для «кп», результат должен быть «Джон» и «Джонатон».

Я читал о TRIE, но это хорошо для префиксов.

Благодаря

Answer 1

Для большинства людей, их адресная книга собирается меньше, чем 1000 записей в ней. Вы можете определенно пройти с помощью поиска подстроки «hn» в каждом имени, в свою очередь.

Что-то подобное, в Python:

results = [name for name in address_book if name.contains(search_term)] 

Answer 2

Если я разрабатываю свой проект, это будет мое решение; Приведенный ниже код является просто псевдокодом, вы можете попробовать это на любом языке программирования

result; 
booklist; 
search_keyword; 
if(length(search_keyword) == 1) //people generaly types first char of the name to find him/his in their list. 
    for i=0 to n //traverse 0 to n 
     if(booklist[i][0] == search_keyword[0]) //check first letter with booklist element and search_keyword 
      result.push(booklist[i]); 

if(length(search_keyword) == 2) //people generaly types first two letter of the name to find him/his in their list. 
    for i=0 to n //traverse 0 to n 
     if(booklist[i][0] == search_keyword[0] AND booklist[i][1] == search_keyword[1]) //check first letter with booklist element and search_keyword 
      result.push(booklist[i]); 

if(length(search_keyword) > 2) 
    for i=0 to n //traverse 0 to n 
     if(booklist[i].contains(search_keyword)) 
      result.push(booklist[i]); 

return result; 

В этом алгоритме, большинство пользователей будут ждать O (п) сложность.

Answer 3

В телефонной книге, как правило,

1. Количество записей не так велико.

2. Записи добавляются/удаляются/изменяются, гораздо реже, чем обыскиваются.

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

Например, предположим, что вы добавляете новую запись с длиной n. Эта запись не более n подстроки. Для каждой такой подстроки:

1. Если это не в хеш-таблице, добавьте запись, сопоставляющую подстроку, в пустой список.

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

Если у вас есть м слова, и самое длинное слово п, то O (м п) должно быть достаточно, чтобы хранить все. Для обычной телефонной книги это крошечный.