1786번: 찾기
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m
www.acmicpc.net
kmp 알고리즘에 대해서는 위의 블로그에 설명이 아주 잘 되어있다.
KMP : 문자열 검색 알고리즘
문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했
bowbowbow.tistory.com
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | import sys def getpi(p): j = 0 pi = [0] * len(p) for i in range(1, len(p)): while j > 0 and p[i] != p[j]: j = pi[j-1] if p[i] == p[j]: j += 1 pi[i] = j return pi def kmp(t, p): ans = [] refac = getpi(P) j = 0 for i in range(len(t)): while j > 0 and t[i] != p[j]: j = refac[j-1] if t[i] == p[j]: if j == len(p)-1: ans.append(i-len(p)+1) j = refac[j] else: j += 1 return ans T = sys.stdin.readline() P = sys.stdin.readline() T = T[0:-1] P = P[0:-1] answer = kmp(T, P) print(len(answer)) for i in answer: print((i+1), end= ' ') | cs |
'알고리즘' 카테고리의 다른 글
| [BOJ] 1918 후위표기식 - 문자열, 스택 (0) | 2020.11.02 |
|---|---|
| [BOJ] 2668 단지번호붙이기 - dfs, graph (0) | 2020.11.01 |
| [BOJ] 1629 곱셈 - 분할정복 (0) | 2020.10.29 |
| [BOJ] 12016 가장 긴 증가하는 부분수열 - 이분탐색 (0) | 2020.10.29 |
| [BOJ] 9251 LCS - DP, 문자열 (0) | 2020.10.29 |