목차
지침
순진한 방법
효율적인 방법
아이디어
구현
출력
결론
백엔드 개발 C++ 주어진 바이너리 문자열에서 동일한 길이의 부분 문자열을 선택하여 주어진 기능을 최대화하십시오.

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

Aug 28, 2023 am 09:49 AM
하위 문자열 이진 문자열 최대화하다

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

길이가 같은 두 개의 이진 문자열 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25 : Myrise에서 모든 것을 잠금 해제하는 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

Jul 25, 2023 am 09:45 AM

MySQL에서 LOCATE 함수를 사용하여 문자열에서 하위 문자열의 위치를 ​​찾는 방법 MySQL에는 문자열을 처리하는 데 사용할 수 있는 함수가 많이 있습니다. 그 중 LOCATE 함수는 문자열에서 부분 문자열의 위치를 ​​찾는 데 사용할 수 있는 매우 유용한 함수입니다. LOCATE 함수의 구문은 다음과 같습니다. LOCATE(substring,string,[position]) 여기서 substring은 찾을 하위 문자열이고 string은 찾을 하위 문자열입니다.

Java에서 부분 문자열의 발생 횟수를 재귀적으로 계산합니다. Java에서 부분 문자열의 발생 횟수를 재귀적으로 계산합니다. Sep 17, 2023 pm 07:49 PM

두 개의 문자열 str_1과 str_2가 주어졌습니다. 목표는 재귀 프로시저를 사용하여 문자열 str1에서 하위 문자열 str2의 발생 횟수를 계산하는 것입니다. 재귀 함수는 정의 내에서 자신을 호출하는 함수입니다. str1이 "Iknowthatyouknowthatiknow"이고 str2가 "know"인 경우 발생 횟수는 -3입니다. 예를 들어 str1="TPisTPareTPamTP", str2="TP"를 입력하면 Countofoccurrencesofasubstringrecursi가 출력됩니다.

strtok_r() 함수는 C 언어의 함수로 문자열을 일련의 하위 문자열로 분할하는 것입니다. strtok_r() 함수는 C 언어의 함수로 문자열을 일련의 하위 문자열로 분할하는 것입니다. Aug 26, 2023 am 09:45 AM

이 함수는 strtok() 함수와 유사합니다. 유일한 주요 차이점은 재진입 함수라고 불리는 _r입니다. 재진입 기능은 실행 중에 중단될 수 있는 기능입니다. 이 유형의 함수를 사용하여 실행을 재개할 수 있습니다. 따라서 재진입 기능은 스레드로부터 안전합니다. 즉, 손상을 일으키지 않고 스레드에 의해 안전하게 중단될 수 있습니다. strtok_r() 함수에는 context라는 추가 매개변수가 있습니다. 이렇게 하면 기능을 올바른 위치에 복원할 수 있습니다. strtok_r() 함수의 구문은 다음과 같습니다: #include<string.h>char*strtok_r(char*string,constchar*limiter,char**

C++로 작성되어 1로 시작하는 이진 문자열의 고유 순열 수를 찾습니다. C++로 작성되어 1로 시작하는 이진 문자열의 고유 순열 수를 찾습니다. Sep 05, 2023 am 09:01 AM

주어진 문제에서는 0과 1로 구성된 문자열이 주어집니다. 1로 시작하는 모든 순열의 총 개수를 찾아야 합니다. 대답은 엄청난 숫자일 수 있으므로 모듈로 1000000007을 가져와 출력합니다. Input:str="10101001001"Output:210Input:str="101110011"Output:56 우리는 몇 가지 조합 수학을 적용하고 몇 가지 공식을 설정하여 이 문제를 해결할 것입니다. 풀이 방법 이 방법에서는 0과 1의 개수를 세어보겠습니다. 이제 n이 문자열에 나타나는 1의 수이고 m이 문자열에 나타나는 0의 수라고 가정합니다.

이진 문자열에서 증가하지 않는 가장 긴 하위 시퀀스 이진 문자열에서 증가하지 않는 가장 긴 하위 시퀀스 Sep 07, 2023 pm 11:13 PM

이 문제에서는 주어진 문자열에서 증가하지 않는 가장 긴 부분 수열을 찾아야 합니다. 증가하지 않는다는 것은 문자가 동일하거나 내림차순임을 의미합니다. 이진 문자열에는 "0"과 "1"만 포함되므로 결과 문자열은 "1"로 시작하고 "0"으로 끝나거나 "0" 또는 "1"로 시작하고 끝나야 합니다. 이 문제를 해결하기 위해 문자열의 각 위치에서 접두사 "1"과 접미사 "0"을 세고 접두사 "1"과 접미사 "0"의 최대 합을 찾습니다. 문제 설명 - 바이너리 문자열 str이 제공됩니다. 주어진 문자열에서 증가하지 않는 가장 긴 부분 수열을 찾아야 합니다. 예 입력–str="010100"Output–4는 가장 긴 비재귀를 보여줍니다.

PHP에서 pack() 함수의 기능은 데이터를 이진 문자열로 변환하는 것입니다. PHP에서 pack() 함수의 기능은 데이터를 이진 문자열로 변환하는 것입니다. Aug 31, 2023 pm 02:05 PM

pack() 함수는 데이터를 이진 문자열로 압축합니다. 구문 pack(format,args) 매개변수 format - 사용할 형식입니다. 다음은 가능한 값입니다. - a - NUL 패딩 문자열 A - 공백 패딩 문자열 h - 16진수 문자열, 낮은 니블 먼저 H - 16진수 문자열, 높은 니블 먼저 c - 부호 있는 문자 C - 부호 없는 문자 s - 부호 있는 짧은(항상 16비트) , 머신 바이트 순서) S - unsigned short(항상 16비트, 머신 바이트 순서) n - unsigned short(항상 16비트, big endian 바이트 순서) v - unsigned short(항상 16비트, little endian 바이트 순서) i - 부호 있는 정수 (머신 크기 및 바이트 순서에 따라 다름) I - 없음 부호 있는 정수(머신 크기 및 바이트 순서에 따라 다름)

PHP 정규 표현식: 문자열에서 특정 문자를 마지막 부분 문자열로 추출하는 방법 PHP 정규 표현식: 문자열에서 특정 문자를 마지막 부분 문자열로 추출하는 방법 Jun 22, 2023 pm 05:33 PM

정규식은 특정 패턴의 문자열을 일치시키는 데 사용할 수 있는 강력한 텍스트 처리 도구입니다. PHP에서 정규식은 문자열 처리, 양식 유효성 검사, 검색 및 바꾸기 등에 일반적으로 사용됩니다. 이 기사에서는 PHP의 정규 표현식을 사용하여 문자열에서 마지막 부분 문자열까지 특정 문자를 추출하는 방법을 소개합니다. 먼저, 예를 살펴보겠습니다. "http://"로 시작하는 여러 URL을 포함하는 문자열 $str이 있고 이러한 URL을 추출하여

PHP는 다른 문자열에 있는 문자열의 시작 위치부터 끝 ​​위치까지 문자열을 반환합니다. PHP는 다른 문자열에 있는 문자열의 시작 위치부터 끝 ​​위치까지 문자열을 반환합니다. Mar 21, 2024 am 10:31 AM

이 글은 PHP가 다른 문자열에서 문자열의 시작 위치부터 끝 ​​위치까지 문자열을 반환하는 방법을 자세히 설명합니다. 편집자는 이것이 꽤 실용적이라고 생각하므로 참고용으로 공유하겠습니다. 이 기사에서 뭔가를 얻을 수 있습니다. PHP에서 substr() 함수를 사용하여 문자열에서 부분 문자열을 추출합니다. substr() 함수는 문자열에서 지정된 범위 내의 문자를 추출할 수 있습니다. 구문은 다음과 같습니다. substr(string,start,length) 여기서: string: 하위 문자열을 추출할 원래 문자열입니다. start: 하위 문자열의 시작 위치에 대한 인덱스입니다(0부터 시작). 길이(선택 사항): 하위 문자열의 길이입니다. 지정하지 않은 경우

See all articles