주어진 바이너리 문자열에서 동일한 길이의 부분 문자열을 선택하여 주어진 기능을 최대화하십시오.

길이가 같은 두 개의 이진 문자열 str1과 str2가 주어지면 주어진 문자열에서 같은 길이의 부분 문자열을 선택하여 주어진 함수 값을 최대화해야 합니다. 주어진 기능은 이렇습니다 -

fun(str1, str2) = (len(하위 문자열))/(2^xor(sub1, sub2)).

여기서 len(substring)은 첫 번째 부분 문자열의 길이이고 xor(sub1, sub2)는 주어진 부분 문자열의 XOR입니다. 이는 이진 문자열이므로 가능합니다.

예

으아악 으아악

지침

해를 찾기 위해 다양한 문자열 세트를 선택할 수 있지만 두 문자열 모두에서 "101"을 선택하면 XOR 0이 되어 함수가 최대값을 반환하게 됩니다.

으아악 으아악

지침

이 출력을 생성하는 하위 문자열로 "1"을 선택할 수 있으며, 다른 문자열을 선택하면 더 낮은 값이 생성됩니다.

순진한 방법

이 방법에서는 모든 하위 문자열을 찾은 다음 비교하여 해를 찾게 되지만 이 해법은 효율적이지 않고 시간과 공간의 복잡성이 많이 걸립니다.

길이 x의 하위 문자열을 생성하는 평균 시간 복잡도는 N^2이며, 각 하위 문자열을 비교하는 데에는 N^2의 비용이 더 듭니다. 또한 주어진 하위 문자열의 XOR도 찾아야 하며 이는 N의 추가 요소를 요합니다. 이는 N^5가 위 코드의 시간 복잡도가 된다는 것을 의미하며 이는 매우 비효율적입니다.

효율적인 방법

아이디어

여기서 아이디어는 XOR 값이 높아질수록 항상 답이 줄어든다는 간단한 관찰에서 비롯됩니다. 따라서 함수 반환 값을 최대화하기 위해서는 XOR 값을 최대한 줄여야 합니다.

두 부분 문자열이 모두 0인 경우 달성할 수 있는 최소 XOR 값은 0입니다. 따라서 이 문제는 실제로 가장 긴 공통 부분 문자열 문제에서 파생됩니다.

XOR이 0일 때 피제수 부분은 1이므로 최종 답은 가장 큰 공통 부분 문자열의 길이가 됩니다.

구현

문제 해결 아이디어를 살펴보았습니다. 코드를 구현하는 단계를 살펴보겠습니다.

• 주어진 두 문자열을 입력으로 받아들이고 최종 결과가 될 정수 값을 반환하는 함수를 만들겠습니다.

• 함수에서는 먼저 문자열의 길이를 구한 다음 주어진 문자열에 크기를 곱한 2D 벡터를 만듭니다.

• 중첩된 for 루프를 사용하여 문자열을 반복하고 가장 큰 공통 하위 문자열을 얻습니다.

• 각 반복마다 두 문자열의 현재 인덱스가 일치하는지 확인한 다음 두 문자열의 마지막 인덱스 벡터에서 값을 가져옵니다.

• 그렇지 않으면 벡터의 현재 인덱스를 0으로 설정합니다.

• 또한 공통 하위 문자열의 최대 길이 수를 유지하기 위한 변수를 유지 관리합니다.

• 마지막으로 답변을 반환하고 메인 함수에 인쇄해 보겠습니다.

예

으아악

출력

으아악

시간과 공간의 복잡성

위 코드의 시간 복잡도는 중첩된 for 루프를 사용하고 매번 N번 반복하기 때문에 O(N^2)입니다.

2차원 배열을 사용하여 요소를 저장하므로 위 코드의 공간 복잡도는 O(N^2)입니다.

결론

이 튜토리얼에서는 주어진 바이너리 문자열에서 동일한 길이의 하위 문자열을 선택하여 주어진 함수의 최대 점수를 구현하도록 코딩합니다. 우리는 이미 매우 비효율적인 이 순진한 접근 방식에 대해 논의했습니다. 주어진 함수에 따르면 XOR의 값이 더 작으므로 O(N^2) 시간 복잡도에서 가장 긴 공통 부분 문자열을 가져와 XOR을 0으로 만듭니다.

위 내용은 주어진 바이너리 문자열에서 동일한 길이의 부분 문자열을 선택하여 주어진 기능을 최대화하십시오.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!