자바에서 n 개의 문자열 비교

Question

일치하는 문자열의 수를 n 개의 문자열과 비교하는 가장 빠른 방법을 아는 사람이 있습니까?

예 : "example"이라는 단어는 일치 검색을 위해 n 개의 단어가 포함 된 목록과 비교해야합니다. 목록에는 길이에 제한없이 여러 단어가 포함될 수 있습니다.

내가 할 수있는 특정 알고리즘이 있습니까? Boyer-Moore Algorithm과 같이 문자열 내에서 부분 문자열을 찾는 문자열 일치 알고리즘을 알고 있습니다. 하지만 이건 아니야. 제발 도와주세요. 자바에서 이것을 구현할 것임을 주목하라.

Answer 1

당신은 당신의 목록의 Map<Int,List<String>>을 준비 할 수 등호() 방법을 사용하여 각 요소를 비교 동일한 해시 코드를 가진 모든 문자열을 포함합니다.

그러면 새 문자열에 대한 해시 코드를 조회하고 반환 된 목록의 각 문자열에서 equals()를 실행합니다.

비교할 항목이 훨씬 적어지면 훨씬 빨라야합니다. 준비에는 약간의 시간이 필요하므로 두 번 이상 수행해야하는 경우에만 수행하십시오.

Answer 2

contains 메서드를 사용할 수 있습니다.

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

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

Answer 3

실행 목록의 끝까지 루프와 키가 문자열과 목록에 대한 .hashcode()입니다

Answer 4

정확한 일치를 확인하려는 경우 사전의 해시지도를 유지하고 단어의 해시를 찾거나 각 노드가 문자 인 http://en.wikipedia.org/wiki/Trie과 같은 트리를 사용할 수 있습니다.

둘 다 단어의 수에 비해 거의 일정한 시간 복잡성을 가지며 대신 찾고있는 단어의 길이에 따라 다릅니다 (중요하지 않음).