크기가 작은 부분 문자열
(https://school.programmers.co.kr/learn/courses/30/lessons/147355)
기본 개념
- 문자열
t의 길이:N(예:N = t.length) - 찾고자 하는 부분 문자열
p의 길이:M(예:M = p.length)
t에서 길이가 M인 부분 문자열을 모두 찾으려고 할 때, 부분 문자열이 시작할 수 있는 마지막 인덱스는 N - M다. 부분 문자열이 t의 끝까지 정확히 M 길이를 유지하기 위해서는, 시작 인덱스가 N - M 이어야만 한다.
- 문자열
t: "12345" (N=5) - 부분 문자열
p: "678" (M=3)
여기서 t에서 길이가 3인 모든 부분 문자열을 찾으려면, "123", "234", "345"가 되어야 한다. 시작 인덱스는 각각 0, 1, 2이다. 여기서 볼 수 있듯이, 시작 인덱스 2는 N - M (5 - 3 = 2)과 일치한다. N - M 이상의 인덱스에서 시작하면, 길이 M을 만족하는 부분 문자열을 완성할 수 없게 된다.
부분 문자열이 가능한 "시작 위치의 개수"를 구하는 공식
부분 문자열이 가능한 "시작 위치의 개수"는 실제로 N - M + 1이다. 이는 시작 인덱스가 0부터 계산될 때, 마지막으로 가능한 시작 인덱스인 N - M을 포함해야 하기 때문.
이 개념은 문자열 검색, 문자열 매칭 문제에서 매우 중요하며, 문자열을 다루는 다양한 알고리즘(예: KMP, Rabin-Karp)에서 기본으로 사용되는 아이디어다. 문자열의 부분 집합을 탐색하거나, 특정 패턴을 문자열 내에서 찾을 때 이러한 원리를 기반으로 계산하게 된다.
크기가 작은 부분 문자열
(https://school.programmers.co.kr/learn/courses/30/lessons/147355)
기본 개념
- 문자열
t의 길이:N(예:N = t.length) - 찾고자 하는 부분 문자열
p의 길이:M(예:M = p.length)
t에서 길이가 M인 부분 문자열을 모두 찾으려고 할 때, 부분 문자열이 시작할 수 있는 마지막 인덱스는 N - M다. 부분 문자열이 t의 끝까지 정확히 M 길이를 유지하기 위해서는, 시작 인덱스가 N - M 이어야만 한다.
- 문자열
t: "12345" (N=5) - 부분 문자열
p: "678" (M=3)
여기서 t에서 길이가 3인 모든 부분 문자열을 찾으려면, "123", "234", "345"가 되어야 한다. 시작 인덱스는 각각 0, 1, 2이다. 여기서 볼 수 있듯이, 시작 인덱스 2는 N - M (5 - 3 = 2)과 일치한다. N - M 이상의 인덱스에서 시작하면, 길이 M을 만족하는 부분 문자열을 완성할 수 없게 된다.
부분 문자열이 가능한 "시작 위치의 개수"를 구하는 공식
부분 문자열이 가능한 "시작 위치의 개수"는 실제로 N - M + 1이다. 이는 시작 인덱스가 0부터 계산될 때, 마지막으로 가능한 시작 인덱스인 N - M을 포함해야 하기 때문.
이 개념은 문자열 검색, 문자열 매칭 문제에서 매우 중요하며, 문자열을 다루는 다양한 알고리즘(예: KMP, Rabin-Karp)에서 기본으로 사용되는 아이디어다. 문자열의 부분 집합을 탐색하거나, 특정 패턴을 문자열 내에서 찾을 때 이러한 원리를 기반으로 계산하게 된다.
