Лучшая структура данных для словаря в Java (а также Python)

Question

Вот мое требование:

• Вход: Случайная строка достаточно длинной Ex: fdjhkajajkfdj
• Выход: fdj имеет 2 вхождения и разделенные x символы

я хочу поставить все три буквы слова в массиве и проверить, если они одинаковы Например:

a[0] = fdj 
a[1] = djh 
a[2] = jhk 
a[3] = hka 
a[4] = kaj 
. 
. 
. 
a[n] =fdj 

Мой ответ a[0] и a[n] совпадений, может быть более двух раз.

Вопрос: Итак, какой массив следует использовать, который является оптимальным в этой ситуации. Я использую Java (а также python). Я думал о Дикте.

Answer 1

В Java можно использовать интерфейс Map (http://download.oracle.com/javase/1.4.2/docs/api/java/util/Map.html)

я хотел бы использовать HashMap, так что ключ является 3 буквы слова и значение является счетчиком появлений. Вот некоторые примеры кода псевдо

HashMap<String, int> wordCountMap = new HashMap<String, int>(); 
for(....) // for each 3 letter word in the input 
{ 
    String word = ...; // current three letter word 
    if(wordCountMap.containsKey(word)) 
     wordCountMap.put(word, wordCountMap.get(word)++); 
    else 
     wordCountMap.put(word, 1); 
} 

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

Чтобы вернуть количество символов между словами, вы можете сделать это отдельно после подсчета событий с помощью манипуляции с строками (см. String.indexOf). Псевдо-код для этого ....

String orginalInput = "fdjhkajajkfdj"; 
String word = "fdj"; 
int firstOccurance = originalInput.indexOf(); 
int secondOccurance = originalInput.indexOf(firstOccurance+1); 
int charsInBetween = secondOccurance - firstOccurance - 3; // difference in indices minus length of word 

Answer 2

В Python диктофон в порядке.

В Java, вы можете использовать HashSet, если вам нужно определить только первый матч, но если вы хотите, чтобы подсчитать количество совпадений, вы можете использовать карту

Edit: вы изменили параметры вопрос, так вот что я предлагаю сейчас. Используйте Map> - ключ - это трехбуквенное слово, и вы поддерживаете список значений индекса, которые возникают в строке. Вы можете использовать эквивалент в Python

Answer 3

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

Answer 4

Ну. fdj будет соответствовать, потому что это первые 3 символа строки? Или это происходит откуда-то еще? Если у вас более 2 вхождений вашего needle, вам нужно расстояние между первыми 2-мя матчами, или первым, и последним, или все расстояния для каждой пары матчей?

Ну, я могу дать вам функцию, которая даст вам все матчи.

>>> def find_matches(needle, hackstay): 
... '''returns a list of positions of needle in hackstay''' 
... ptr = 0 
... found = [] 
... while True: 
...  idx = hackstay[ptr:].find(needle) 
...  if idx < 0: return found 
...  found.append(ptr+idx) 
...  ptr += idx+len(needle) 
... 
>>> 
>>> 
>>> find_matches('fdj','fdjhkajajkfdj') 
[0, 10] 

Расстояние между двумя элементами массива - это только больший элемент минус меньший элемент минус длина иглы.

Пример:

>>> res = find_matches('fdj','fdjhkajajkfdj') 
>>> distance = abs(res[0]-res[1])-len('fdj') 
>>> print distance 
7 

С этим вы можете решить сами, где needle приходит и какие расстояния вам нужно. Надеюсь, поможет!

PS: Если кто-нибудь может предложить, как улучшить этот код, пожалуйста, сделайте это! Мое чувство говорит, что это можно записать короче (например, используя found = [i for ??? if ???]), но я не знаю, как.

Answer 5

Ваш способ хранения трех буквенных слов в массиве НЕ эффективен. Пожалуйста, рассмотрите возможность хранения строки в дереве суффикса или просто в массиве и используйте алгоритм KMP, чтобы найти максимальное количество строк, которые вы должны искать. Позже подсчеты могут быть сохранены, однако вы выбираете.