문제 이해문제 자체는 정말 단순하다. 긴 문자열이 쭉 주어지고, pattern이라는 짧은 문자열이 주어졌을 때 긴 문자열 안에서 pattern이 몇 번 반복되는지 찾는 문제이다. 하지만 단순한 문제에 그렇지 않은 설명 길이를 보면 어려운 문제임을 직감할 수 있다. 이 문제가 어려운 이유는 시간 복잡도 때문 일 것이다. 단순히 접근한다면 패턴 길이만큼을 패턴과 같은지 체크하면서 한 칸씩 전진하면 될 것이다. 물론 해결이 가능하지만 문제 설명에 쓰여 있는 것과 같이 시간 복잡도를 만족시킬 수 없다.더 효율적인 코드가 필요하고, 이를 위한 대표적인 문자열 알고리즘으로는 Boyer-Moore, Rabin-Karp, KMP 등이 있다. 그 중에서 이번에는 KMP 알고리즘으로 문제를 해결해보자. 실제 코드def ..
