목록Algorithm/Algorithms (1)
블로그 옮겼습니다
Z algorithm
Z algorithm 은 문자열관련 알고리즘이다. 우선 Z Array 라는 것이 있다. Z[i] 의 정의는 아래와 같다. Z[i] : S[i...] 의 prefix 들 중 S의 prefix이기도 한 녀석들 중 길이가 가장 긴녀석의 길이즉, i에서 시작하는 S의 부분 문자열들 중 S의 prefix 이기도 한 녀석들 중 가장 긴 길이이다. 이 Z Array 를 O(|S|) 의 시간에 구할 수 있게 해주는 것이 Z algorithm 이다. 우선 이 것을 알면 KMP와 같이 문자열 검색이 선형시간에 가능하다. 즉, 어떤 긴 문자열 S에서 특정 패턴 P가 등장하는 위치를 모두 구하는 것이 Z 알고리즘을 활용하여 O(S + P) 에 가능한데 이 방법은 나중에 아래에서 설명하겠다. 그리고 가끔 이런 문제들이 있다. ..
Algorithm/Algorithms
2017. 9. 8. 15:38