K 비트만 포함하는 하위 문자열을 설정하여 이진 문자열의 해밍 거리를 최소화합니다.

같은 길이의 두 문자열 사이의 해밍 거리는 해당 위치에서 다른 값이 있는 모든 위치의 수입니다. 다음 예를 통해 이해할 수 있습니다.

S= “ramanisgoing”

중국어 번역:

S= “ramanisgoing”

T=“dishaisgoing”

여기서 5는 두 문자열 S와 T 사이의 해밍 거리입니다. Raman과 disha는 문자열의 차이를 동일하게 만드는 두 단어이기 때문입니다.

문제 설명

그러나 이 문제에서는 이진수만 포함하는 두 문자열 사이의 해밍 거리를 찾아야 합니다. 사용자는 하나의 문자열(S라고 가정)과 다른 문자열(T라고 가정)을 제공합니다. 처음에는 이 문자열이 '0' 비트만 포함하고 주어진 문자열의 크기와 같다고 가정합니다. 부분 문자열이 요소로 '1'로만 구성될 수 있는 요소 수를 나타내는 값을 나타내는 숫자 'k'를 얻습니다. 따라서 크기 k의 부분 문자열을 문자열(T)에 배치합니다. 둘 사이의 해밍 거리를 최소화하는 모든 위치 하위 문자열 S와 T.

몇 가지 예를 통해 이 문제를 이해해 보겠습니다.

입력 − S = "100111" K = 5

출력 - 3

Explanation − 초기 문자열 T는 "000000"과 동일하며 문자열 T는 문자열 S와 비교하여 k=5일 때 최소 해밍 거리를 찾기 위해 다음과 같이 변경됩니다: "111110" 및 " 011111" .

100111에서 000000 사이의 해밍 거리는 4입니다. 100111에서 111110 사이의 해밍 거리도 3이고, 100111에서 011111 사이의 해밍 거리도 3입니다.

그러나 3은 4보다 작기 때문에 최소 해밍 거리는 3이 됩니다. 그러므로 우리의 대답은 3이다.

- S = "100101" K = 5

- 3

− 초기 문자열 T는 "000000"과 같으므로 문자열 T는 문자열 S와 비교하여 k=5일 때 최소 해밍 거리를 찾기 위해 다음과 같이 변경됩니다: "111110" 및 "011111 ".

100101과 000000 사이의 해밍 거리는 3입니다. 100101과 111110 사이의 해밍 거리도 4이고, 100101과 011111 사이의 해밍 거리도 4입니다.

그러나 3은 4보다 작기 때문에 최소 해밍 거리는 3이 됩니다. 그러므로 우리의 대답은 3이다.

문제 설명

이 문제를 이해하고 해결책을 찾아봅시다.

해결책 1 잔인한 해결책

가능한 모든 문자열 중에서 가장 작은 해밍 거리를 얻기 위해 시작점과 끝점이 다른 부분 문자열의 위치를 ​​변경하여 문자열 T를 수정하겠습니다.

예

다음은 위 방법의 C++ 프로그램 구현입니다.

으아아아

출력

으아아아

솔루션 2 최적화 계획

알고리즘

• 접두사 합계 배열을 사용하여 1의 수를 계산하고 이를 최소 해밍 거리로 저장합니다

• 문자열 S를 탐색하여 문자열 S에 있는 K개의 서로 다른 하위 문자열 사이의 값을 찾습니다.

• 만약 (i-1

• 이전 해밍 거리와 현재 해밍 거리 사이의 최소값을 찾아 최소값을 저장합니다.

• 현재 해밍 거리는 (K - v) 하위 문자열의 0 요소 수와 현재 S 하위 문자열의 0 수를 연산하여 찾을 수 있습니다

• 마지막으로 전체 최소 거리를 반환합니다.

예

다음은 위 방법을 C++ 프로그램으로 구현한 것입니다

으아아아

출력

으아아아

결론

이 기사에서는 최소 해밍 거리를 찾기 위해 먼저 간단한 방법을 살펴보겠지만 시간 복잡도를 개선하기 위해 루프 반복 횟수에서 피할 수 있는 접두사와 배열 개념을 사용할 것입니다.

위 내용은 K 비트만 포함하는 하위 문자열을 설정하여 이진 문자열의 해밍 거리를 최소화합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!