몇 줄의 문자열이 있고 모든 접두사에 대해 가장 일반적인 접미사 10 개를 찾고 싶습니다. 그것에 대한 효율적인 알고리즘이 있습니까?효율적인 가장 일반적인 접미사 알고리즘입니까?
확실한 해결책은 다음과 같습니다
- 스토어
<string, count>
쌍 목록을 분류. - 우리가 검색하는 접두사에 대한 이진 검색 범위로 식별하십시오.
- 이 범위에서 가장 높은 숫자는
count
입니다. - 모든 짧은 접두사에 대해 사전 계산이 가능하므로 데이터의 많은 부분을 볼 필요가 없습니다.
실제로 그렇게 효율적인지 확실하지 않습니다. 내가 간과 한 더 나은 방법이 있습니까?
답변은 실시간이어야하지만 필요한만큼 사전 처리가 필요할 수 있습니다.
사용중인 특정 언어는 무엇입니까? C++ 또는 Java로 추측 할 수 있습니다 ... 또한 DB에있는 문자열 또는 파일에있는 문자열입니까? – nico
그것은 모든 파일이고 어떤 언어가 가장 빠르므로 거의 확실합니다. – taw