주어진 바이너리 문자열에서 동일한 길이의 부분 문자열을 선택하여 주어진 기능을 최대화하십시오.
길이가 같은 두 개의 이진 문자열 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

핫 AI 도구

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

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

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

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

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

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

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

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

뜨거운 주제











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

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

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

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

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

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의 정규 표현식을 사용하여 문자열에서 마지막 부분 문자열까지 특정 문자를 추출하는 방법을 소개합니다. 먼저, 예를 살펴보겠습니다. "http://"로 시작하는 여러 URL을 포함하는 문자열 $str이 있고 이러한 URL을 추출하여

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