Сравнение n строк в java

-2

Кто-нибудь знает самый быстрый способ сравнения одной строки с n количеством строк для совпадения?Сравнение n строк в java

Например: слово «пример» необходимо сравнить со списком, содержащим n количество слов, для соответствия. Список может содержать любое количество слов любой длины.

Есть ли конкретный алгоритм, который я могу использовать для этого? Я знаю алгоритмы соответствия строк, которые находят подстроку внутри строки, такую как алгоритм Boyer-Moore. Но не для этого. Пожалуйста, помогите мне здесь. Обратите внимание, что я буду реализовывать это на Java.

источник

2012-03-12 Prerak Pradhan

Является ли список слов отсортированным или индексированным каким-либо образом? В противном случае вам просто нужно сделать вас Boyer-Moore для каждого из них в цикле. – Thilo

Какой матч? Ответы предполагают, что под «совпадением» вы подразумеваете «найти точно такую же строку», а не подстроку, например. – Thilo

строки не отсортированы в любом случае, и да, я пытаюсь получить точное соответствие (нечувствительное к регистру) –

Вы можете подготовить Map<Int,List<String>> для вашего списка, где ключевым является .hashcode() для строки и списка содержит все строки с тем же хэш-кодом.

Затем вы просто просматриваете hashcode для своей новой строки и запускаете equals() для каждой строки в возвращаемом списке.

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

источник

2012-03-12 08:23:05

, пожалуйста, объясните, как сделать эту работу для нечувствительного к регистру соответствия (см. Комментарии к вопросу). – Thilo

Если строки могут быть уменьшены и все еще имеют смысл, то строчные буквы перед обработкой. –

Вы можете использовать метод contains.

List<String> lstr = Arrays.asList(new String[]{"a", "b", "c", "d", "e"}); 
Collections.sort(lstr); 

lstr.contains("c"); // true 
lstr.contains("f"); // false

источник

2012-03-12 07:29:32 MByD

Не работает с нечувствительным к регистру совпадением (см. Комментарии к вопрос). – Thilo

Выполнить цикл до конца списка и сравнить каждый элемент, используя Equals() метода

источник

2012-03-12 07:31:49 Raj

+1 или equalsIgnoreCase в этом случае. Также, возможно, выйдут на первый матч. – Thilo

Предполагая, что вы просто хотите проверить точное соответствие, вы можете либо сохранить хеш-карту своего словаря, либо просмотреть хеш слова, либо использовать дерево типа http://en.wikipedia.org/wiki/Trie, где каждый узел является буквой.

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

источник

2012-03-12 08:33:00 Supr

Предполагается, что вам нужно сделать это несколько раз для того же списка. – Thilo

Сравнение n строк в java

ответ

Смежные вопросы