Overview
BOJ 16916번 부분 문자열 Python 문제 풀이
분류: String (문자열)
문제 페이지
https://www.acmicpc.net/problem/16916
풀이 코드 1
s, p = (input().rstrip() for _ in range(2))
print([0, 1][p in s])
가장 간단한 풀이.
in 메소드를 이용하여 p 문자열이 s 문자열에 들어있는지 여부를 파악한다.
풀이 코드 2
s, p = (input().rstrip() for _ in range(2))
print([0, 1][s.__contains__(p)])
문자열 자료형이 가지고 있는 __contains__(str) 메소드를 활용한 방법
풀이 코드 3 - KMP 알고리즘
from sys import stdin
from typing import List
def make_table(p: str) -> List[int]:
table = [0] * len(p)
j = 0
for i in range(1, len(table)):
while j > 0 and p[i] != p[j]:
j = table[j - 1]
if p[i] == p[j]:
j += 1
table[i] = j
return table
def kmp(s: str, p: str, table: List[int]) -> bool:
i, j = 0, 0
for i in range(len(s)):
while j > 0 and s[i] != p[j]:
j = table[j - 1]
if s[i] == p[j]:
j += 1
if j == len(p):
return True
return False
def main():
s = stdin.readline().rstrip()
p = stdin.readline().rstrip()
table = make_table(p)
print([0, 1][kmp(s, p, table)])
if __name__ == "__main__":
main()KMP 알고리즘을 이용한 풀이.
String Matching 알고리즘 중 하나인 Knuth-Morris-Pratt algorithm을 이용하였다.
먼저 Failure function (위 코드에서는 make_table())을 계산하고, 이를 토대로 문자열 s에 패턴 p 가 존재하는지 탐색해나간다.
Failure function 계산의 시간 복잡도는 O(m)이고, KMP 알고리즘을 통한 패턴 탐색은 O(m + n)의 시간 복잡도를 가진다.
풀이 코드 4 - Boyer Moore 알고리즘
from sys import stdin
from typing import List
# character jump에 사용하기 위하여 p에서 각 문자 위치를 저장한 테이블 생성
# (Last-Occurrence Function)
def set_table(p: str) -> List[int]:
table = [-1] * 26
for i in range(len(p) - 1, -1, -1):
if table[ord(p[i]) - 97] == -1:
table[ord(p[i]) - 97] = i
return table
def character_jump(s: str, p: str, s_idx: int, p_idx: int, table: List[int]) -> int:
l = table[ord(s[s_idx]) - 97]
if l >= 0:
return s_idx + len(p) - min(p_idx, 1 + l)
else:
return s_idx + len(p)
def boyer_moore(s: str, p: str) -> bool:
i, j = len(p) - 1, len(p) - 1
table = set_table(p)
while i < len(s):
if s[i] == p[j]:
if j == 0:
# i 번째에서 String Match
return True
else:
i -= 1
j -= 1
else:
i = character_jump(s, p, i, j, table)
j = len(p) - 1
return False
def main():
s = stdin.readline().rstrip()
p = stdin.readline().rstrip()
print([0, 1][boyer_moore(s, p)])
if __name__ == "__main__":
main()
Boyer-Moore Algorithm 응용한 String Matching 기법이다. 실제 Boyer-Moore Algorithm과는 다를 수 있다.
채점 결과 시간초과가 발생하였다.
해당 알고리즘은 아래 두 가지 Heuristic 전략을 사용한다.
1. Looking-Glass Heuristic: 문자열 s와 패턴 p를 비교할 때, p의 뒤에서부터 비교한다.
2. Character-jump heuristic: 미스매치가 발생하였을 때, 다음 비교 위치를 찾는 방법. 미스매치된 문자열 s의 문자가 패턴 p에 존재하는 경우 해당 위치로 점프하고, 그렇지 않으면 p의 길이 만큼 건너뛴다. 이를 위해 Boyer-Moore 알고리즘을 이용하기 전에 Last-Occurence Function을 구현한다.
Last-Occurence Function은 O(m + s)의 시간복잡도를, Boyer-Moore 알고리즘은 O(nm + s)의 시간복잡도를 가진다. s는 문자열 종류의 개수로, 본 문제의 입력으로는 알파벳 소문자만 들어오므로 26이 된다. 일반적으로 Boyer-Moore 알고리즘은 영문과 같은 문자열 탐색에서 빠른 성능을 보여준다. 하지만 아래와 같은 worst case에서는 시간이 오래걸린다.
s = aaa ... a
p = baaa따라서 이미지, DNA 염기 서열에서 패턴 매칭 방법으로 해당 알고리즘을 이용한다면 성능이 낮을 수 있다.
