주어진 문자열을 가지고, 나는 Manacher의 알고리즘을 사용하여 개의 회문 부속 문자열의 수를 선형 시간으로 찾는 법을 안다. 하지만 지금은 고유/고유 번호 회문 하위 문자열을 찾아야합니다. 이제 이것으로 O (n + n^2) 알고리즘이 생길 수 있습니다. 하나의 'n'은 이러한 부분 문자열을 모두 찾았고, n^2는 이미 발견 된 부분 문자열과 비교하여 고유한지 확인합니다.개개의 회문 부속 문자열의 수
더 나은 알고리즘이있는 것이 확실합니다. 나는 접미사 나무로 나의 운을 시험해보고 있을지 생각하고 있었다? 더 복잡한 알고리즘이 있습니까?
동일한 결과를 두 번 보관하지 못하도록 해시 테이블에 찾은 부분 문자열을 넣을 수 있습니다.
해시 테이블에 대한 액세스 시간은 O (1)입니다.
나는 부분 문자열 그 자체가 아니라 선형 시간에 그러한 하위 문자열의 _number_을 찾는 방법을 안다. 기본적으로 저는 Manacher 알고리즘에 대해 이야기하고 있습니다. –
@LiamWillis : Wikipedia http://en.wikipedia.org/wiki/Longest_palindromic_substring에는 * number *가 언급되어 있지 않지만 명시 적으로 다음과 같이 명시되어 있습니다. * 그러나 Apostolico, Breslauer & Galil (1995)에 의해 관찰 된 것처럼 동일한 알고리즘이 또한 입력 문자열 내의 모든 최대 palindromic 하위 문자열을 선형 시간으로 다시 찾는 데 사용됩니다. *이 단어에 사용 된 노트 ** find **. 나는 혼란스러워. –
동일한 Manacher 알고리즘에서 중심 주위의 부분 문자열을 찾을 때 @zavg가 제안한대로 해시 테이블에 저장합니다. –
다른 모든 요소와 모든 요소를 비교하면 n²가 발생하지 않습니까? 그래서 저는 그것이 O (n + n²) = O (n²) 일 것이라고 생각합니다. 그럼에도 불구하고 나는 꽤 나쁘다. – CompuChip
@CompuChip 네, 저의 잘못입니다. 편집했습니다. –