반응형 { Problem Solving }/KMP4 [KMP/파이썬] 백준 1097번 : 마법의 문자열 / 플래5 https://www.acmicpc.net/problem/1097 1097번: 마법의 문자열 L개의 문자로 이루어진 문자열 T가 있다. T(i)는 T를 i (0 ≤ i < L)번째 문자부터 시작하게 부터 시작하게 원형 이동한 것이고, 길이는 T의 길이와 같다. 즉, 0 ≤ j < L을 만족하는 모든 j에 대해서, T(i) www.acmicpc.net import itertools n = int(input()) words = [] for _ in range(n): words.append(input()) k = int(input()) def kmp(pattern, all_string): table = [0 for _ in range(len(pattern))] i = 0 for j in range(1, len.. 2022. 4. 8. [KMP] 백준 1305번 : 광고 / 플래 4 https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net size = int(input()) b = input() table = [0 for _ in range(len(b))] i = 0 for j in range(1, len(b)): while i > 0 and b[i] != b[j]: i = table[i-1] if b[i] == b[j]: i += 1 table[j] = i print(size-table[-1]) 초반엔 너무 어렵게 생각해서 감이 안잡혔는데, 파이 .. 2022. 3. 29. [KMP] 백준 1786번 : 찾기 / 플래5 https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net def kmp(all_string, pattern): # kmp_table table = [0 for _ in range(len(pattern))] i = 0 for j in range(1, len(pattern)): while i > 0 and pattern[i] != pattern[j]: i = table[i-1] if pattern[i] == pattern[j]: i += 1 table.. 2022. 3. 29. [KMP] 백준 16916번 : 부분 문자열 / 골드 3 https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net KMP를 몰랐다면 시간때문에 좀 힘들었을 것 같으나, 난 KMP를 공부했기 때문에 쉽다. def kmp(all_string, pattern): # kmp_table table = [0 for _ in range(len(pattern))] i = 0 for j in range(1, len(pattern)): while i > 0 and pattern[i] != pattern[j]: i = table[i-1] if patter.. 2022. 3. 29. 이전 1 다음 반응형
