백준/kmp
-
1305 광고백준/kmp 2022. 6. 18. 22:47
1. 풀이 다른 블로그를 참고했다. kmp 알고리즘에는 주어진 문자열의 부분 문자열 중 접두사와 접미사가 같은 최대 길이를 나타내는 배열을 구한다. 나는 이를 value 배열이라고 표현했다. 이 문제에서 나온 문자열 aabaaa의 value 배열은 [0, 1, 0, 1, 2, 2] 이다. kmp 알고리즘에 대해 자세히 알고 싶다면 다음 내용을 살펴보면 된다. https://happy-fun.tistory.com/253 1786 찾기 1. kmp 알고리즘 문자열 검색 알고리즘(kmp) 에 대해 먼저 자세하게 설명하겠다. 1) 예제 예를 들어 설명하겠다. 문자열 all : ABCDABCDABEF 문자열 part : ABCDABE 가 있을때, all 에 part 문자열이 있는지 확인. happy-fun.tis..
-
1786 찾기백준/kmp 2022. 6. 13. 21:03
1. kmp 알고리즘 문자열 검색 알고리즘(kmp) 에 대해 먼저 자세하게 설명하겠다. 1) 예제 예를 들어 설명하겠다. 문자열 all : ABCDABCDABEF 문자열 part : ABCDABE 가 있을때, all 에 part 문자열이 있는지 확인해보자. 문자열 all의 길이를 N, 문자열 part의 길이를 M이라고 했을 때, 한 글자씩 모두 비교하면, 시간복잡도는 O(N*M) 으로 매우 오래 걸리지만, 이 방법을 사용하면, O(N+M) 으로 짧아지게 된다. 2) value 배열 일단 value 배열을 만들 것이다. 이 배열은, 문자열 part의 0~i번째까지 부분 문자열 중 접두사와 접미사가 같은 최대 길이이다. 즉, 아래와 같다. 이 배열을 왜 만들었는지는 아래에서 좀 더 살펴보면 알 수 있을 것이..