주어진 문장에서 부분 문자열 S2가 발생한 후에 부분 문자열 S1이 나타나는지 확인합니다.

이 문제에서는 주어진 문자열 S에서 하위 문자열 S2가 발생한 후에 하위 문자열 S1이 발생하는지 확인해야 합니다. 문자열 S에서 S1과 S2의 시작 인덱스를 비교하여 이 문제를 해결할 수 있습니다. p>

문제 설명 - S, S1, S2라는 세 개의 하위 문자열이 제공됩니다. 문자열 S에는 항상 S1이 하위 문자열로 포함됩니다. 주어진 문자열 S에서 부분 문자열 S1이 부분 문자열 S2 뒤에 나타나는지 확인해야 합니다.

예

Enter – S = “abxtutorialspointwelcomepoint”, S1 = “환영합니다”, S2 = “포인트”

Output – 예

설명 – 문자열 S에서 "점" 하위 문자열이 2번 나타납니다. 하나는 "환영합니다" 앞에 있고 다른 하나는 "환영합니다" 뒤에 있습니다. 따라서 문자열 S2가 발생한 후에 문자열 S1이 발생한다고 말할 수 있습니다.

Input– S = "abcdefgh", S1 = "abcd", S2 = "gh";

Output – 아니요

설명S1은 문자열 S의 시작 부분에 있습니다. 따라서 S1은 하위 문자열 S2 뒤에 나타나지 않습니다.

Enter – S = “abce”, S1 = “bc”, S2 = “xy”

Output – 아니요

Explanation – 문자열 S에는 문자열 S2가 존재하지 않으므로 No.를 인쇄합니다.

방법 1

이 방법에서는 S2 하위 문자열의 모든 시작 인덱스를 찾아 컬렉션에 저장합니다. 그 후 S1의 시작 인덱스를 얻습니다. S2의 각 시작 인덱스를 S1의 시작 인덱스와 비교하고 집합의 값이 S2의 시작 인덱스보다 작은 경우 하위 문자열 S1이 하위 문자열 S2가 발생한 후에 발생한다고 말할 수 있습니다.

알고리즘

• 부분 문자열 S2의 시작 인덱스를 저장하는 컬렉션을 정의합니다.

• find() 메서드를 사용하여 S2 하위 문자열의 첫 번째 시작 인덱스를 찾습니다.

• while 루프를 사용하여 하위 문자열 S2의 모든 시작 인덱스를 가져오고 insert() 메서드를 사용하여 컬렉션에 저장합니다.

• 설정된 값을 순회합니다. 주어진 문자열 S에서 하위 문자열 S1의 시작 인덱스보다 작은 값이 있으면 true를 반환합니다.

• 마지막으로 false를 반환합니다.

예

으아악

출력

으아악

시간 복잡도 - O(N*K), 문자열 S2의 시작 인덱스를 찾아야 하기 때문입니다.

공간 복잡도 - 문자열 S2의 시작 인덱스를 저장하므로 O(N)입니다.

방법 2

이 방법에서는 문자열을 반복합니다. 문자열 S에는 항상 문자열 S1이 포함되어 있으므로 S2가 S1보다 먼저 발생하는 경우 true를 반환합니다.

알고리즘

• 변수의 길이를 저장하려면 len, n1 및 n2 변수를 정의하세요.

• 문자열 탐색을 시작하세요.

• 'temp 문자열을 정의하고 i번째 인덱스에서 시작하여 길이가 n2인 하위 문자열로 초기화합니다.

• temp == S2이면 true를 반환합니다.

• i번째 인덱스부터 길이가 n1인 하위 문자열을 가져옵니다. temp == s1이면 false를 반환합니다.

• 마침내 true를 반환합니다.

예

으아악

출력

으아악

시간 복잡도 – O(N*min(n1, n2)), 길이가 n1과 n2인 부분 문자열을 찾았기 때문입니다.

공간 복잡도 - 부분 문자열을 저장하므로 O(min(n1, n2)입니다.

첫 번째 방법에서는 컬렉션을 사용하여 S2의 시작 인덱스를 저장하는데, 이는 두 번째 방법의 코드보다 더 많은 공간을 필요로 합니다. 두 번째 방법의 코드는 첫 번째 방법보다 읽기 쉽습니다. 또는 프로그래머는 S1이 나타난 후에 하위 문자열 S2가 나타나는지 확인하는 문제를 해결하려고 시도할 수 있습니다.

위 내용은 주어진 문장에서 부분 문자열 S2가 발생한 후에 부분 문자열 S1이 나타나는지 확인합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!