BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/16916
16916번: 부분 문자열
첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.
www.acmicpc.net
내가 작성한 코드
import sys
read = sys.stdin.readline
s = read().rstrip()
p = read().rstrip()
def make_table(s: str) -> list[int]:
table = [0] * len(s)
j = 0
for i in range(1, len(s)):
c = s[i]
while j > 0 and s[j] != c:
j = table[j-1]
if s[j] == c:
j += 1
table[i] = j
return table
table = make_table(p)
i = ans = 0
for c in s:
while i > 0 and p[i] != c:
i = table[i - 1]
if p[i] == c:
i += 1
if i == len(p):
ans = 1
break
print(ans)
- KMP로 패턴의 중복까지 확인하여 탐색
- ababc 패턴을 abababc에서 찾을 때, 탐색 실패시 패턴의 처음부터 찾으면 탐색을 실패함
다른 사람이 작성한 코드
def getPI(pattern):
j = 0
for i in range(1, len(pattern)):
while j > 0 and pattern[i] != pattern[j]:
j = pi[j - 1]
if pattern[i] == pattern[j]:
j += 1
pi[i] = j
def KMP(s, pattern):
getPI(pattern)
j = 0
for i in range(len(s)):
while j > 0 and s[i] != pattern[j]:
j = pi[j - 1]
if s[i] == pattern[j]:
if j == len(pattern) - 1:
return True
else:
j += 1
return False
s = input()
pattern = input()
pi = [0 for x in range(len(pattern))]
if KMP(s, pattern):
print('1')
else:
print('0')
- 비슷하게 구현했다
https://www.landlordgang.xyz/82
[백준 16916 파이썬] 부분 문자열(KMP 알고리즘)
www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져
www.landlordgang.xyz
기억해야할 것
- KMP 알고리즘 활용
- 여러 문자열 문제를 풀었는데, 많이 사용되는 것 같다
- 특정 문자열의 포함을 확인할 때는 필수
- 단순 brute-force로는 패턴 내의 중복이 고려되지 않음
- KMP 알고리즘 이해
- 문자열의 포함 관계를 확인할 때 사용
- 등장 인물
- 문자열
- 패턴
- table - 문자열
- 탐색의 대상이 되는 문자열, 문자의 일치 여부로만 확인 - 패턴
- (주인공) table을 작성할 때도 사용하고, 인덱스가 종료를 확인하거나 알고리즘에 중요한 역할 - table
- 패턴의 탐색에서 중복 확인에 사용
'코딩테스트' 카테고리의 다른 글
[백준][부분집합] 집합의 표현 (0) | 2021.08.12 |
---|---|
[백준][구간합] 구간 합 구하기 (0) | 2021.08.12 |
[프로그래머스][KAKAO_BLIND][2018] 파일명 정렬 (0) | 2021.08.11 |
[백준][문자열] Cubeditor (0) | 2021.08.11 |
[프로그래머스][KAKAO_BLIND][2020] 문자열 압축 (0) | 2021.08.10 |