Redddy's Devlog

🔈 문제 You are given a 0-indexed integer array nums of size n, and a 0-indexed integer array pattern of size m consisting of integers -1, 0, and 1. A subarray nums[i..j] of size m + 1 is said to match the pattern if the following conditions hold for each element pattern[k]: nums[i + k + 1] > nums[i + k] if pattern[k] == 1. nums[i + k + 1] == nums[i + k] if pattern[k] == 0. nums[i + k + 1] < nums[i..

문자열 $N$ 와 $H$가 주어졌을 때 $N$에 $H$ 있는지 찾는 문자열 검색 알고리즘에 대해 알아보자. 나이브하게 접근해보면 $N$의 첫문자부터 마지막문자까지 $H$와 하나하나 비교해가면서 일치하는지 판별할 수 있고 해당 솔루션의 시간복잡도는 $O(|N|*|H|)$ 이다. 문자열의 길이가 짧다면 해당 접근방법도 구현도 쉽고 나쁘지만은 않다. 하지만 문자열의 길이가 커진다면 제한시간내에 동작하지 못하게 된다. $N[k...i-1]$과 $H[...i-1]$ 까지는 문자열이 일치하였지만 $H[i]$ 문자에서 일치하지 않는경우 다시 $N[k+1]$ 부터 비교하는 것이 아니라 이미 $H[...i-1]$까지 어떤 문자가 있는지 알고 있으니 보지 않아도 $H[k+1]$이 $H[0]$과 같은지 다른지는 알 수 있지..