online_z_algo.hpp¶
字符逐个加入时在线维护 Z 函数；适合流式字符串的前缀匹配长度。
Complexity: Time: \(O(n)\) total for \(n\) appends with constant-time symbol operations. A single add can be \(O(n)\); query is \(O(1)\). Space: \(O(n)\) state, plus the returned finalized indices.
Source: maspy
AC 记录：zalgorithm。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n) total for n appends with constant-time symbol operations.
/// A single add can be O(n); query is O(1).
/// Space: O(n) state, plus the returned finalized indices.
#include <string>
#include <vector>
namespace noya {
/// @brief Online Z-algorithm: compute Z-values incrementally as characters are appended.
template <class S> struct online_z_algo {
std::vector<std::vector<int>> mp;
std::vector<int> z;
std::vector<S> str;
int p;
online_z_algo() { p = 1; }
/// @brief Append c at i == str.size(); return indices fixed by this mismatch.
/// Positions reaching the current end remain unfinished; index 0 is never emitted.
/// Input length must fit in int; symbols need coherent != and copying.
std::vector<int> add(int i, S c) {
str.push_back(c);
int len = str.size();
z.push_back(-1);
mp.emplace_back();
std::vector<int> end;
if (len == 1) {
return end;
}
if (str[0] != c) {
z[i] = 0;
end.push_back(i);
}
auto del = [&](int j) {
z[j] = i - j;
mp[i].push_back(j);
end.push_back(j);
};
while (p <= i) {
if (z[p] != -1) {
p += 1;
} else if (str[i - p] != str[i]) {
del(p);
p += 1;
} else {
break;
}
}
if (p < i) {
for (auto j : mp[i - p]) {
del(j + p);
}
}
return end;
}
/// @brief Current longest prefix match at 0 <= i < str.size(); query(0) is the length.
int query(int i) {
if (z[i] == -1) {
return str.size() - i;
}
return z[i];
}
};
} // namespace noya
// NOYA_ONLINEZALGO_HPP
#ifndef NOYA_ONLINEZALGO_HPP
#define NOYA_ONLINEZALGO_HPP 1
/// @complexity Time: O(n) total for n appends with constant-time symbol operations.
/// A single add can be O(n); query is O(1).
/// Space: O(n) state, plus the returned finalized indices.
#include <string>
#include <vector>
namespace noya {
/// @brief Online Z-algorithm: compute Z-values incrementally as characters are appended.
template <class S> struct online_z_algo {
std::vector<std::vector<int>> mp;
std::vector<int> z;
std::vector<S> str;
int p;
online_z_algo() { p = 1; }
/// @brief Append c at i == str.size(); return indices fixed by this mismatch.
/// Positions reaching the current end remain unfinished; index 0 is never emitted.
/// Input length must fit in int; symbols need coherent != and copying.
std::vector<int> add(int i, S c) {
str.push_back(c);
int len = str.size();
z.push_back(-1);
mp.emplace_back();
std::vector<int> end;
if (len == 1) {
return end;
}
if (str[0] != c) {
z[i] = 0;
end.push_back(i);
}
auto del = [&](int j) {
z[j] = i - j;
mp[i].push_back(j);
end.push_back(j);
};
while (p <= i) {
if (z[p] != -1) {
p += 1;
} else if (str[i - p] != str[i]) {
del(p);
p += 1;
} else {
break;
}
}
if (p < i) {
for (auto j : mp[i - p]) {
del(j + p);
}
}
return end;
}
/// @brief Current longest prefix match at 0 <= i < str.size(); query(0) is the length.
int query(int i) {
if (z[i] == -1) {
return str.size() - i;
}
return z[i];
}
};
} // namespace noya
#endif // NOYA_ONLINEZALGO_HPP
/// @complexity Time: O(n) total for n appends with constant-time symbol operations.
/// A single add can be O(n); query is O(1).
/// Space: O(n) state, plus the returned finalized indices.
#include <string>
#include <vector>
namespace noya {
/// @brief Online Z-algorithm: compute Z-values incrementally as characters are appended.
template <class S> struct online_z_algo {
std::vector<std::vector<int>> mp;
std::vector<int> z;
std::vector<S> str;
int p;
online_z_algo() { p = 1; }
/// @brief Append c at i == str.size(); return indices fixed by this mismatch.
/// Positions reaching the current end remain unfinished; index 0 is never emitted.
/// Input length must fit in int; symbols need coherent != and copying.
std::vector<int> add(int i, S c) {
str.push_back(c);
int len = str.size();
z.push_back(-1);
mp.emplace_back();
std::vector<int> end;
if (len == 1) {
return end;
}
if (str[0] != c) {
z[i] = 0;
end.push_back(i);
}
auto del = [&](int j) {
z[j] = i - j;
mp[i].push_back(j);
end.push_back(j);
};
while (p <= i) {
if (z[p] != -1) {
p += 1;
} else if (str[i - p] != str[i]) {
del(p);
p += 1;
} else {
break;
}
}
if (p < i) {
for (auto j : mp[i - p]) {
del(j + p);
}
}
return end;
}
/// @brief Current longest prefix match at 0 <= i < str.size(); query(0) is the length.
int query(int i) {
if (z[i] == -1) {
return str.size() - i;
}
return z[i];
}
};
} // namespace noya
// NOYA_ONLINEZALGO_HPP