동적 프로그래밍을 사용하여 주어진 문자열에서 다른 회문 부분 문자열 찾기

소개

이 튜토리얼에서는 입력 문자열을 사용하여 가능한 모든 회문 부분 문자열을 찾는 방법에 대해 논의했습니다. 이 작업 방법을 구현하기 위해 C++ 프로그래밍 언어와 해당 기능을 사용합니다.

회문은 앞에서 뒤로, 뒤에서 앞으로 읽어도 같은 문자열입니다. 예를 들어 Mom은 회문 문자열입니다. 이 튜토리얼에서는 문자열을 가져와서 그 안에 있는 가능한 모든 회문 하위 문자열을 찾습니다.

예제 1

의 중국어 번역은 다음과 같습니다.

예제 1

으아악

출력

으아악

위의 예에서 입력 문자열은 'a', 'b', 'c', 'aa', 'aaa', 'aba' 및 'aca' 등 7개의 회문 하위 문자열을 생성할 수 있습니다.

예 2

의 중국어 번역은 다음과 같습니다.

예 2

으아악

출력

으아악

위의 예에서는 입력 문자열을 사용하여 길이가 1인 회문 부분 문자열 4개만 얻을 수 있습니다. 입력 문자열에 반복되는 문자가 없으므로 길이가 1보다 큰 하위 문자열은 없습니다.

예시 구현에 사용된 함수

• size() − 이는 주어진 문자열의 문자 수를 반환하는 문자열과 유사한 함수입니다. 매개변수를 허용하지 않습니다.

문법

으아악

예

으아악

• begin() − 이 라이브러리 함수는 STL에 정의되어 있습니다. 지도 컨테이너의 시작 반복 값을 제공합니다.

구문: map_name.begin(); 예: mp.begin();

• end() − 이 라이브러리 함수는 STL에 정의되어 있습니다. 맵 컨테이너의 최종 반복 값을 제공합니다.

문법

으아악

예

으아악

• substr() − 입력 문자열을 사용하여 하위 문자열을 생성합니다. string.h 헤더 파일에 정의되어 있습니다. 두 개의 매개변수(pos, len)를 허용합니다. Pos는 하위 문자열의 시작 값이고 len은 하위 문자열의 문자 수입니다.

문법

으아악

예

으아악

알고리즘

• 주어진 문자열을 고려하고 그 안에 있는 모든 회문 하위 문자열을 찾으세요.

• 문자열을 반복하여 입력 문자열의 모든 회문 하위 문자열을 찾습니다.

• 홀수 및 짝수 길이의 회문 부분 문자열에 대해 두 개의 배열을 만듭니다.

• 두 배열의 값을 해시 맵에 저장합니다.

• 해시맵에 저장된 모든 값을 인쇄합니다.

• 부분 문자열의 수는 해시 맵의 길이와 같습니다. 해시 맵을 반복하고 각 값을 인쇄합니다. for 루프를 사용하여 맵의 각 항목에 액세스하고 관련 값을 인쇄합니다. 마지막으로 출력되는 값의 개수는 해시 맵의 크기와 일치해야 합니다.

로직 1 예

이 섹션에서는 C++ 프로그래밍 언어의 개념을 사용하여 위 예제 중 하나를 구현합니다. main() 함수에서 입력 문자열을 고려하고 이를 사용하여 출력을 생성합니다.

으아악

출력

으아악

로직 2 예

동적 프로그래밍 방법을 사용하여 또 다른 예제를 구현하고 있습니다. 동적 프로그래밍에서는 작업을 하위 작업으로 나누고 개별적으로 해결하여 시간과 복잡성을 줄입니다.

으아악

출력

으아악

결론

이 튜토리얼에서는 주어진 문자열에서 가능한 모든 회문 하위 문자열을 찾는 두 가지 방법을 개발했습니다. 두 가지 예제를 통해 작업을 이해하고 C++ 프로그래밍 언어를 사용하여 샘플 코드를 작성합니다. 예제를 구현하기 위해 해시 맵과 벡터를 사용하여 회문 부분 문자열을 저장합니다. 해시 맵을 사용하면 키 값 쌍을 일치시키는 데 도움이 되며 요구 사항에 따라 많은 해시 함수를 사용할 수 있습니다. 또한 예제를 구현하기 위해 일부 라이브러리 함수를 사용했습니다.

위 내용은 동적 프로그래밍을 사용하여 주어진 문자열에서 다른 회문 부분 문자열 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!