기초 코드를 하나씩 알아보도록 합시다.

---

배열

문자열

투 포인터 접근 방식을 대표적으로 만들 수 있다.

부분 문자열 확인

Q1. 두 문자열 s와 t를 받아서 s가 t의 부분 문자열인지 확인한다. 부분 수열(subsequence)문제.

해시맵을 관리하거나 시퀀스의 길이를 추적하지 않아도 된다.
일치하는 문자를 찾을 때까지 end 포인터를 증가시키면 된다.
일치하는 문자를 찾으면 더 이상 일치하는 항목이 없을 때까지 begin 포인터를 증가시킨다.

입력 예시 : s="abc", t="a1b2c3" 이면 True 반환

def is_subsequence(text, query):
	len_query, len_text = len(query), len(text)
    begin, end = 0,0
    
    while begin < len_query and end < len_text:
    	if query[begin] == text[end]:
        	begin += 1
        end += 1
        
    return begin == len_query
    
    
    

Q2. "programming"에서 "gram"은 연속된 문자열이므로 부분 문자열을 검사한다. 부분 문자열(substring) 문제.

in 연산자를 사용하지 않고 부분 문자열(substring)을 찾는 알고리즘은 두 가지 주요 방법이 있다: 브루트포스(Brute-force) 알고리즘과 KMP(Knuth-Morris-Pratt) 알고리즘이다.

아래는 브루트포스 알고리즘이다. 시간 복잡도는 완전탐색 방식이라 최악의 경우 $O(mn)$이다.

def is_substring_bruteforce(text, query):
    len_text = len(text)
    len_query = len(query)
    
    # 텍스트의 모든 가능한 시작점을 순회
    for i in range(len_text - len_query + 1):
        # 현재 시작점부터 쿼리 길이만큼의 부분 문자열을 비교
        if text[i : i + len_query] == query:
            return True
            
    return False
    

해시 테이블