PS하는 kdy

지난 글에서 KMP 알고리즘의 원리와 시간복잡도를 알아보았고, 이를 바탕으로 문자열을 검색하는 기본 문제를 풀어보았다. 이번 글에서는 KMP 알고리즘을 활용하는 문제들을 몇 가지 살펴볼 것이다. https://www.acmicpc.net/problem/1305 문제는 단순하다. 광고 문구가 AABA이고 광고판이 9글자까지 표현 가능하다면 광고판에는 광고 문구를 반복해서 이어붙인 문자열이 보이고, 1칸씩 이동하는 형태이다. 즉, 아래와 같이 광고판에 문구가 뜨는 것이다.[A A B A][A A B A][A A B A][A A B A][A A B A][A A B A][A A B A][A A B A][A A B A] 광고판의 어느 순간의 모습이 주어지면 광고 문구로 ..

문자열 알고리즘 블로그의 첫 시작은 KMP로 정했다. KMP 알고리즘은 해결하고자 하는 문제 상황 자체가 매우 단순하고 기초적이기 때문에 첫 시작으로 적합하다는 생각이 들었다. 이번 글에서는 KMP 알고리즘의 원리에 대해 다루고자 하며, 다음 글에서는 KMP 알고리즘을 활용하는 문제들을 다양하게 다뤄보고자 한다. KMP 알고리즘(Knuth - Morris - Pratt Algorithm)은 특정 패턴이 문자열의 어디에서 나타나는지 빠르게 찾기 위한 문자열 검색 알고리즘이다. 자세한 내용은 아래 문제에서 확인하자. 먼저 아래 문제를 살펴보자. https://www.acmicpc.net/problem/1786 문제 상황은 문자열 내에서 다른 문자열이 어디에 속해 있는지 모두 찾는 것이다. 우리가 자주 사용하..