정리하기 위한 블로그 정리하기 위한 블로그

Z[i] : s의 i 부터의 substring == s의 prefix 가 되는 최대 길이 Z 배열 :문자열 s의 Z배열 z[i]는 s[i]에서 시작하는 부분 문자열이면서 s의 prefix이기도 한 가장 긴 문자열의 길이를 담는 배열이다.이전에 구한 정보들을 최대한 활용해서 O(n)에 Z배열을 구할 수 있다.  문자열 ABCABCABAB인 경우 Z 배열ABCABCABABx005002020  vector z_function(const string &s) { int n = s.size(); vector z(n); z[0] = n; int L = 0, R = 0; for (int i = 1; i   prefix과 일치하는 substring 중 가장 긴 substring의 인덱스 l,r..