Z 알고리즘을 사용하여 주어진 문자열에서 모든 단어 발생을 제거합니다.

이 기사에서는 "Z 알고리즘을 사용하여 주어진 문자열에서 모든 단어 발생 제거"라는 흥미로운 문자열 조작 문제를 자세히 설명합니다. 이 문제는 패턴 검색 문제에 Z 알고리즘을 적용한 좋은 사례로 그 효율성이 부각됩니다. 이에 대해 자세히 살펴보겠습니다.

문제 설명

문자열 S와 단어 W가 주어지면 Z 알고리즘을 사용하여 S에서 W를 모두 제거하는 작업이 수행됩니다.

문제 이해하기

문자열 S = "HelloWorldHelloWorld"와 단어 W = "World"를 생각해 보세요. 목표는 S에서 W를 모두 제거하는 것입니다. 따라서 출력은 "HelloHello"가 됩니다.

Z-알고리즘

Z 알고리즘은 선형 시간 내에 텍스트에서 패턴의 모든 발생을 찾을 수 있습니다. 주어진 인덱스 i에 대해 Z[i]는 문자열의 접두사이기도 한 i에서 시작하는 가장 긴 부분 문자열의 길이를 나타내는 배열(Z 배열)을 구성합니다.

알고리즘 방법

문제 해결 단계는 다음과 같습니다. -

• 새 문자열 P = W + '$' + S를 만듭니다.

• Z 알고리즘을 P에 적용하고 Z 배열을 구성합니다.

• Z 배열을 반복합니다. Z[i]가 W의 길이와 같다면 해당 인덱스에 W가 존재한다는 의미입니다. 해당 인덱스의 S에서 W를 제거합니다.

Example

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

Example

위 메서드를 구현하는 C++ 코드는 다음과 같습니다.

으아아아

출력

으아아아

테스트 케이스 예시

예를 들어보겠습니다 -

S = "Iamwritingwriting", W = "writing"이라고 가정합니다. 프로그램은 "Iam"을 인쇄합니다. 그 이유는 다음과 같습니다 −

• 새 문자열 P는 "writing$Iamwritingwriting"이 됩니다.

• Z 알고리즘을 적용하면 Z[8]과 Z[15]가 W의 길이와 동일하다는 것을 알 수 있습니다. 이는 W가 S의 이러한 인덱스에 존재한다는 것을 의미합니다.

  李>

• 그런 다음 S에서 이 인덱스의 W를 제거하고 "Iam" 문자열을 얻습니다.

결론

Z 알고리즘은 패턴 검색 문제를 해결하는 강력한 도구입니다. 이 기사에서는 문자열에서 모든 단어를 제거하는 데 적용되는 것을 살펴보았습니다. 이 질문은 문자열 일치 알고리즘을 이해하고 적용하면 얻을 수 있는 이점을 보여주는 좋은 예입니다. 알고리즘을 이해하고 학습하면 복잡한 문제를 해결할 수 있는 방법이 열린다는 점을 항상 기억하세요.

위 내용은 Z 알고리즘을 사용하여 주어진 문자열에서 모든 단어 발생을 제거합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!