Ukkonen 알고리즘을 사용하여 가장 긴 공통 부분 문자열, 가장 긴 회문 부속 문자열, 가장 긴 반복 부분 문자열, 모든 패턴 검색 및 하위 문자열 검사를 KMP와 접미사 트리로 모두 찾을 수 있습니까? 그렇다면 두 알고리즘 모두 선형 시간 복잡성을 가지고 있기 때문에 어느 것을 사용해야합니까?시간 복잡성에 대한 Ukkonen의 알고리즘을 사용하는 Knuth-Morris-Pratt (KMP)와 접미사 트리의 차이.
가장 긴 공통 부분 문자열을 찾으려면 선형 복잡도를 갖는 Kadane의 알고리즘을 사용합니다. 가장 긴 Palindromic Substring의 경우 선형 복잡도를 갖는 Manacher 알고리즘이 선택됩니다. 반복되는 문자열과 모든 패턴을 검색하기 위해, 예는 KMP와 Boyer-Moore 사이에서 선택의 여지가 있습니다. Boyer-Moore가 맨 끝에 일치하지 않으면 처음부터 일치시키지 않아도된다는 가정하에 첫 번째 패턴 대신 마지막 패턴과 패턴이 일치합니다. KMP는 불일치가 발생하면 이전에 매칭 된 문자의 재 검사를 우회하는 관찰을 이용하여 메인 텍스트 스트링 S 내의 단어 W의 발생을 검색한다. 이렇게하면 ACTGT와 같은 작은 세트에 대해 KMP가 약간 더 최적화됩니다.
숙제 문제입니까? 그리고 지금까지 어떤 연구를 해왔습니까? – AgataB
아니요, 숙제 문제가 아닙니다. 나는 그것에 대해 조금 연구를했다. –