주어진 단어의 더블 서브 워드를 찾는 알고리즘

주어진 단어 V의 서브 워드 U는 형태가 u = ww 일 때 double입니다. 예를 들어 "abab"는 "acdababx"의 더블 서브 워드이지만 "cdab"는 그렇지 않습니다.주어진 단어의 더블 서브 워드를 찾는 알고리즘

단어 V의 주어진 하위 워드 U가 double인지 확인하는 알고리즘이 필요합니다. V는 선형 시간으로 사전 처리 될 수 있지만, 모든 V에 대해 많은 U가있을 것이기 때문에 특정 U에 대한 응답은 일정한 시간 복잡성을 가져야합니다. U는 간격으로 주어집니다 (예 : V = "acdababx", 간격 [3 ..6]는 하위 단어 "daba"에 해당합니다.

예 입출력 :

V = abbacbacca

U =

[1-4] -> 없음
[3-8] -> 예
[5 8] -> 아니오
[8 9] -> 예
[1 10] -> N o

현재 대회에서 문제가되지 않습니다.

출처

2011-03-30 KCH

그래서'u -> ww'는'w' 만 두 번 사용하도록 보장됩니까? – Argote

또는 더 흥미로운 ... 문자열의 모든 이중 부분 문자열을 찾는 방법? –

@Argote : u = ww를 쓰면 나는 u가 그 자체에 추가 된 단어라는 것을 의미합니다. @ belisarius : 문자열의 모든 double 부분 문자열을 찾는 작업은 O (n^2) 시간에 쉽게 수행 할 수 있지만 n이 클 수 있기 때문에 너무 느립니다. – KCH

입력 단어의 접미사 트리 (O (n)에서 구성 할 수 있음)에서 모든 더블 단어의 끝점을 표시하거나 (일반적으로 문학, 직렬 반복)) 시각. 물론이 기사에 대한 전체 액세스 권한이 없기 때문에 O (1) 쿼리 시간을 만족 시킬지 확실하지 않습니다.

용지는 다음과 같습니다 도움이 Linear time algorithms for finding and representing all the tandem repeats in a string

희망.

출처

2011-03-30 23:16:01

주어진 단어의 더블 서브 워드를 찾는 알고리즘

답변

관련 문제