문자열과 쿼리 썸네일형 리스트형 [String] Z-algorithm Z-algorithm 또는 Z-function은 어떠한 string s의 위치 [0, l)에서 string s와의 최대 접두어를 구하는 알고리즘이다. 작동 시간은 O(n)을 자랑한다. string에서의 문자열 검색에 O(n)의 작동시간을 가지는 알고리즘이 뭐가 있었지? 바로 KMP 알고리즘이며, KMP알고리즘을 사용하기 위해 작성하는 부분일치 테이블과 기능적으로 상당히 흡사한 측면이 있다. CP - algorithm 사이트에서는 다음과 같이 기술 되어 있다. The Z-function for this string is an array of length n where the i-th element is equal to the greatest number of characters starting from t.. 더보기 이전 1 다음