문자열에서 정확히 K번 나타나는 길이가 M인 부분 문자열의 개수를 셉니다.

이 기사에서는 컴퓨터 과학 분야의 독특하고 흥미로운 문제인 "문자열에서 정확히 K 번 나타나는 M 길이 부분 문자열 계산"에 대해 자세히 알아볼 것입니다. 이런 유형의 질문은 프로그래밍 대회나 인터뷰에서 자주 묻는 질문입니다. 시작하기 전에 우리가 다루고 있는 것이 무엇인지 정의해 봅시다 -

• Substring− 다른 문자열 내에서 발견된 연속 시퀀스입니다.

• M length− 관심 있는 하위 문자열의 길이입니다.

• K회 − 하위 문자열이 원래 문자열에 나타나야 하는 정확한 횟수입니다.

알고리즘 설명

이 문제를 해결하기 위해 해시 맵(C++에서는 순서가 지정되지 않은 맵이라고도 함)의 기능을 활용하겠습니다. 해시 맵을 사용하면 키-값 쌍의 형태로 데이터를 저장할 수 있으며 검색 및 삽입 작업에 지속적인 시간 복잡성을 제공하므로 이러한 문제를 해결하는 탁월한 도구가 됩니다.

문자열에서 정확히 K번 나타나는 M 길이 부분 문자열을 계산하는 알고리즘은 다음과 같습니다. -

• 빈 해시 맵을 초기화합니다.

• 문자열을 반복하여 가능한 모든 M 길이 하위 문자열을 만듭니다.

• 각 하위 문자열에 대해 해시 맵에 추가하세요. 이미 존재하는 경우 개수를 늘리십시오.

• 모든 하위 문자열이 계산된 후 해시 맵을 반복하여 정확히 K 번 발생하는 모든 하위 문자열을 찾습니다.

C++ 구현

위 알고리즘을 C++로 구현한 것입니다. -

예

으아아아

출력

으아아아

위 코드에서 countSubstrings 함수는 입력 문자열 s, 부분 문자열 길이 M, 발생 횟수 K를 매개변수로 사용합니다. 모든 하위 문자열과 그 발생을 추적하기 위해 순서가 지정되지 않은 맵 count_map을 초기화합니다. 그런 다음 문자열을 반복하여 길이가 M인 가능한 모든 하위 문자열을 생성하고 각 하위 문자열에 대해 맵의 개수를 증가시킵니다. 모든 하위 문자열이 계산되면 맵을 반복하여 정확히 K 번 발생하는 모든 하위 문자열을 계산합니다.

주 함수는 코드 실행이 시작되는 곳입니다. 문자열 s와 M, K의 값을 초기화합니다. 그런 다음 countSubstrings 함수를 호출하고 결과를 인쇄합니다.

테스트 케이스 예시

M=3이고 K=3인 문자열 "abcabcabc"를 고려해 보겠습니다.

여기서 M 길이의 하위 문자열은 "abc", "bca", "cab", "abc", "bca", "cab", "abc"입니다. 분명히 하위 문자열 "abc"는 문자열에서 정확히 3번 나타나므로 프로그램의 출력은 1이 됩니다.

해시 맵을 사용하여 부분 문자열을 계산하는 문제에 대한 이러한 접근 방식은 컴퓨터 과학의 시공간 균형을 보여주는 좋은 예입니다. 하위 문자열과 해당 개수를 저장하기 위해 추가 공간을 사용하면 상수 시간에 발생 횟수를 계산하여 문제의 시간 복잡도를 크게 줄일 수 있습니다.

시간과 공간의 복잡성

이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. 이는 가능한 모든 M 길이 하위 문자열을 생성하기 위해 문자열을 한 번만 반복하기 때문입니다.

해시 맵의 저장 요구 사항으로 인해 공간 복잡도도 O(n)입니다. 최악의 경우 각 하위 문자열은 고유하여 맵에 n개의 서로 다른 항목이 생성됩니다.

결론

이 글에서는 컴퓨터 과학의 일반적인 문제, 즉 문자열에서 정확히 K번 나타나는 M 길이 하위 문자열의 수를 세는 문제를 연구합니다. 우리는 해시 맵을 사용하여 C++에서 효율적인 솔루션을 구현했는데, 이를 통해 지속적인 검색 및 삽입 작업이 가능했습니다. 이 문제는 복잡한 문제를 효과적으로 해결하기 위해 데이터 구조와 알고리즘을 함께 사용할 수 있는 방법을 보여주는 완벽한 예입니다.

위 내용은 문자열에서 정확히 K번 나타나는 길이가 M인 부분 문자열의 개수를 셉니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!