순환 버퍼 비교/검색 알고리즘

원형 버퍼가 동일한 길이의 다른 버퍼 목록의 미러 또는 회전인지 여부를 감지하려고합니다.순환 버퍼 비교/검색 알고리즘

예

주어진 다음 버퍼 3 : 다음

AAABCCCA 
AABCCBAA 
AAAACCAA

:는 제 1 버퍼의 미러 회전 같이 CCBAAAAC가 일치하는 것이다.

현재 모든 순환에서 모든 버퍼를 비교 한 다음 버퍼를 역순으로 다시 수행합니다.

이것은 다음을 요구합니다 : 2*n*i 버퍼 비교. (여기서 n은 2를 비교할 버퍼의 수이고 i는 버퍼의 길이입니다.)

누가 더 빠른 알고리즘을 알고 있습니까?

비교 대상 목록이 늘어났습니다 (목록에없는 목록을 찾음). 버퍼를 어떻게 든 주문할 수있는 방법이 있습니까? 그래서 비교가 더 빨리 이루어질 수 있습니까?

내가 가진 한 가지 아이디어는 각 버퍼의 정렬 된 버전을 저장하는 것이므로 같은 수의 항목이 있는지 빠르게 비교할 수 있습니다.

그러나 '순환 시퀀스'에 의해 어떻게 든 더 일반적인 솔루션이 있습니까?

출처

2013-06-13 Myforwik

중복 검색 패턴을 입력 한 다음 정확하게 일치하는 항목을 찾습니다. ?? –

그것은 본질적으로 내가 말한 것과 같은 것입니다. 패턴 매칭은 n 개의 문자열을 가로 지르는 장소에서 보일 것이며, 2 * n * i에 대해 역으로해야 할 것입니다. 그러나 strstr과 같은 표준 함수를 사용하여 코드를 작성하는 가장 쉬운 방법은 여러분이 말한 것입니다. – Myforwik

각 버퍼에 대해 최소 사전 식 값이 될 때까지 회전 할 수 있습니다.

는 예를 들어, 예를 들어 버퍼는 다음과 같이 회전 수 :

AAABCCCA -> AAAABCCC 
AABCCBAA -> AAAABCCB 
AAAACCAA -> AAAAAACC

이 기본적으로 먼저 가장 낮은 값 항목을 넣는 것을 의미한다. 동점이 있으면 다음 항목 등을 비교하십시오. 이것은 어떤 패턴에 대해서도 고유 한 순서를 부여합니다.

출처

2013-06-13 01:31:19

와우. 왜 내가 이것을 깨닫지 못했는지 모르겠다. 내 머리 속을 돌고있는 많은 완충 대. 나는 그것을 할 수 있고, 그 다음 순서를 사전 식으로 명령 할 수있다. 이것은 내가 이진 탐색을 할 수 있음을 의미한다. 버퍼 비교 횟수는 2 * i * n에서 log (n)로 감소합니다. – Myforwik

회전 된 원본과 회전 된 미러 사이에 최소 사전 식 값을 저장하거나 검색 할 수 있습니다. @Myforwik'log n'이 아니라'i log n '이 될 것입니다. 나는 당신이 [trie] (http://en.wikipedia.org/wiki/Trie)와 같은 구조를 사용하여'O (i)'로 내려갈 수 있다고 생각합니다. – Dukeling

@Myforwik 오, "버퍼 비교". 그러면'log n '이 맞습니다. Trie는 i.t.o 문자 비교이며 버퍼 비교는 아닙니다. 보다 일반적인 방법은 문자 비교를 계산하는 것입니다. – Dukeling

순환 버퍼 비교/검색 알고리즘

답변

관련 문제