소문자 라틴 문자로 구성된 문자열 S가 주어집니다. 나는 각각의 위치 S [i]를 찾길 원합니다. 최대 길이 L [i]는 위치가 '< 인 곳입니다 [i'.. i '+ L [i] -1] = s [i .. i + L [i] -1]이다. 예 : s = ababaab, L = {0,0,3,2,1,2,1}. 나는 시간에 그것을하고 싶다 < O (| S |^2). 문제는 접미어 배열로 해결할 수 있다고 생각하지만 어떻게해야합니까?최대 부분 문자열 검색
이 알고리즘은 약간 다른 문제 (i가 항상 0 인 경우)를 처리하지만 O (| S |)로 실행되지만 ZBlock 알고리즘을 살펴 봐야합니다. 편리하게 수정할 수 있어야합니다.
동적 프로그래밍은 O (| S |^2)에서 부분 문자열 일치의 수정 된 버전을 사용하여이를 해결하지만 사용자는 그러한 솔루션을 찾지 않을 것으로 생각됩니다.
당신이 찾고있는 것을 "가장 긴 이전 요소"라고 부르며이 계산을 위해 2 개의 접미사 배열 알고리즘이있는 Crochemore 및 Ilie의 논문이 있습니다. 좋은 소식은 둘 다 선형 시간이라는 것입니다. 두 번째 알고리즘은 Lcp 테이블을 사용하여 조금 더 쉽게 보입니다.
몇 가지 질문 : 어떤 프로그래밍 언어를 사용하고 있습니까? 아직 시도해 봤니? 문제를 어떻게 해결할 수 있는지에 대해 알고 있습니까? – sergico
프로그래밍 언어는 중요하지 않습니다. 예를 들어 c/C++. 나는 알고리즘에 관심이있다. 나는 배열의 모든 요소를 반복하고 매번 접미사 배열에서 가장 긴 공통 접두사를 현재 위치에서 찾으려고 할 때 바보 같은 생각을 가지고 있습니다. – rodart