KMP알고리즘 2

백준 16172 (나는 친구가 적다(Large))

문제 친구가 적은 성민이는 수업에 결석해도 시험이나 과제에 대한 정보를 제대로 얻을 수 없었다. F 학점을 받을 위기까지 아슬아슬하게 결석일 수를 유지하던 성민이는, 어느 날 갑자기 영문도 모른 채 쪽지시험을 보게 되었다! 갑작스러운 쪽지 시험으로 마음이 급해진 성민이는 매직아이를 사용해 벼락치기를 하기로 한다. 성민이가 듣는 과목의 교과서는, 알파벳 소문자(a-z)와 알파벳 대문자(A-Z)로만 이루어져 있다. 성민이가 교과서에서 찾고자 하는 키워드도 역시 알파벳 소문자와 대문자로만 이루어져 있다. 하지만, 성민이에겐 큰 문제가 생겼다. 결석한 날의 수업 내용을 친구에게 빌려 필기를 하던 중, 교과서에 숫자(0-9)를 적어버린 것이다. 키워드를 찾기 힘들어 패닉에 빠진 성민이는 몇 안 되는 친구인 당신에..

백준 1786 (찾기)

www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i~i+m-1번 문자와 P의 1~m www.acmicpc.net 문제가 길어서 링크를 넣는다. 이 문제에서 풀이 방식을 설명하고 있다. 풀이는 KMP 알고리즘을 이용하면 된다. KMP 알고리즘은 빠르게 같은 문자를 찾는 방식이다. 접두사로 접미사에 얼마나 연속적으로 나오는가를 이용하는 알고리즘이다 시간복잡도가 O(n) 에 가깝기 때문에 많이 사용 되고 있다. bowbowbow.tistory.com/6 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 ..