This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// Z-algorithm
// 各 Suffix と元の文字列との LCP を求める
template <typename ArrayType>
struct Z_algorithm {
ArrayType v;
vector<int> Z;
void build() {
int N = v.size(), i, j;
Z = vector<int>(N);
for(i=1,j=0; i<N; i++) {
int l = i - j;
if(i + Z[l] < j + Z[j]) {
Z[i] = Z[l];
}
else {
int k = max(0, j + Z[j] - i);
while(i + k < N and v[k] == v[i+k]) k++;
Z[i] = k;
j = i;
}
}
Z[0] = N;
}
Z_algorithm(ArrayType v_) : v(v_) {
build();
}
// idx から切り出した Suffix と文字列全体との LCP
int get_lcp(int idx) {
return Z[idx];
}
};
#line 1 "string/str_010_z_algorithm.cpp"
// Z-algorithm
// 各 Suffix と元の文字列との LCP を求める
template <typename ArrayType>
struct Z_algorithm {
ArrayType v;
vector<int> Z;
void build() {
int N = v.size(), i, j;
Z = vector<int>(N);
for(i=1,j=0; i<N; i++) {
int l = i - j;
if(i + Z[l] < j + Z[j]) {
Z[i] = Z[l];
}
else {
int k = max(0, j + Z[j] - i);
while(i + k < N and v[k] == v[i+k]) k++;
Z[i] = k;
j = i;
}
}
Z[0] = N;
}
Z_algorithm(ArrayType v_) : v(v_) {
build();
}
// idx から切り出した Suffix と文字列全体との LCP
int get_lcp(int idx) {
return Z[idx];
}
};