주어진 문자열에 길이가 2 이상인 반복 하위 시퀀스가 ​​있는지 확인하는 C++ 프로그램

문자열이 주어지면 문자열에서 반복되는 길이가 2 이상인 부분 수열을 찾으세요. 하위 시퀀스 요소 번호의 인덱스는 동일한 순서일 수 없습니다.

으아악

이 접근 방식이 다양한 상황에서 어떻게 작동하는지 이해하기 위해 아래 몇 가지 예를 살펴보겠습니다. -

예 1 - str = "PNDPNSP"

Explanation − 여기서는 문자열에 반복되는 하위 시퀀스 "PN"이 있으므로 대답은 참입니다.

예 2 - str = "PPND"

Explanation - 여기서는 문자열에 최소 2개의 길이가 반복되는 하위 시퀀스가 ​​없기 때문에 답이 틀렸습니다.

예 3 − str = "PPNP"

설명 - 여기서는 "PP" 인덱스 0과 1, "PP" 인덱스 1과 3이 존재하고, 사용된 "PP"는 하위 시퀀스에서 순차적으로 다른 인덱스를 가지기 때문에 정답입니다. (0부터 시작하는 인덱스)

무차별 접근 방식

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

무차별 접근 방식

이 방법은 길이 2(최소 길이)의 가능한 모든 하위 시퀀스를 생성하고 발견된 하위 시퀀스로 이 하위 시퀀스를 이미 본 적이 있는지 찾습니다. 하위 시퀀스가 ​​이미 존재하면 true를 반환하고 프로그램을 종료합니다. 그렇지 않으면 반복을 완료한 후 아무것도 찾지 못하면 false를 반환합니다.

최악의 경우에는 이 하위 시퀀스가 ​​존재하지 않을 수 있으며 결국 가능한 모든 결과가 생성됩니다.

두 길이의 부분 수열을 저장합니다. 따라서 O(1) 삽입 및 검색을 달성하기 위해 계산된 하위 시퀀스를 해시한다고 가정하면 이는 O(n^2)가 됩니다. 전체 부분 수열도 O(n^2)이므로 저장 공간도 마찬가지입니다.

수정된 가장 긴 공통 부분 수열(LCS)

LCS 알고리즘은 두 문자열에서 가장 긴 공통 부분 수열을 찾습니다. 2차원 행렬의 반복 방법을 사용하는 표준 동적 프로그래밍 방법입니다. 시간 복잡도는 O(n^2)입니다. 수정된 메소드에서는 주어진 문자열 자체만 검색합니다. 그럼에도 불구하고, 현재 위치의 인덱스가 동일한지 확인해 보겠습니다.

예

아래 C++ 코드를 확인하여 길이가 2 이상인 반복되는 하위 시퀀스를 찾는 데 도움이 되는 수정된 가장 긴 공통 하위 시퀀스 알고리즘을 구현하세요. -

으아악

출력

으아악

물론 시간 및 공간 복잡도는 O(n^2)이지만 첫 번째 방법을 보면 O(1)의 해시를 생성하는 것이 더 우아하고 쉽습니다.

향상된 솔루션

이 방법에서는 이전 방법을 기반으로 몇 가지 관찰을 시도해 보겠습니다.

관찰 1 − 캐릭터가 두 번 이상 나타나면 대답은 항상 참입니다. 왜 그런지 볼까요?

Example - 문자열 str = "AVHJFBABVNHFA"에서 위치 0, 6, 12에 "AAA"가 있습니다. 그래서 인덱스 0과 6에 "AA"가 하위 시퀀스로 있고, 인덱스 6과 12에 "AA"가 하위 시퀀스로 있을 수 있습니다. 다른 것으로.

관찰 2 - 문자가 한 번만 반복되면 결과에 기여할 수 없습니다. 최대 하나의 하위 시퀀스에서만 사용할 수 있기 때문입니다. 작동하지 않습니다 왜냐하면 최소한 두 개의 하위 시퀀스가 ​​필요하기 때문입니다. 따라서 모든 문자를 제거하거나 무시할 수 있습니다. 동시에 일어났습니다.

관찰 3 − 문자열이 회문이고 처음 두 관측이 적용되는 경우 답은 다음과 같습니다. 문자열 길이가 홀수인 경우를 제외하면 항상 false입니다. 왜 그런지 볼까요?

예 - 문자열 str = "PNDDNP"

설명 - 이제 문자 순서가 맞지 않아 절대 찾을 수 없습니다. 하위 시퀀스의 순서가 동일하므로 이는 불가능합니다.

예

위의 세 가지 관찰을 모두 바탕으로 문자열에 한 번 나타나는 모든 문자를 제거한 다음 특정 문자가 두 번 이상 나타나는지 또는 문자열이 회문이 아닌지 확인하면 답이 정확하다는 결론을 내립니다. C++로 구현된 개선된 솔루션을 살펴보겠습니다 -

으아악

출력

으아악

결론

우리는 관찰과 해시를 사용하는 것이 이 문제를 해결하는 가장 좋은 방법이라는 결론을 내렸습니다. 시간 복잡도는 O(n)입니다. 공간 복잡도도 O(n) 정도이므로 새 문자열과 상수 26자 해시가 생성됩니다.

위 내용은 주어진 문자열에 길이가 2 이상인 반복 하위 시퀀스가 ​​있는지 확인하는 C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!