目录
目录
- 马拉车（Manacher）
- Z 函数
- 后缀数组
- 后缀自动机（SAM 新版）
- KMP
马拉车（Manacher）
/** 马拉车（Manacher, with string）* 2024-04-06: https://qoj.ac/submission/380047* 2024-04-09: https://qoj.ac/submission/384389 【模板】
**/
std::vector<int> manacher(std::string s) {std::string t = "#";for (auto c : s) {t += c;t += '#';}int n = t.size();std::vector<int> r(n);for (int i = 0, j = 0; i < n; i++) {if (2 * j - i >= 0 && j + r[j] > i) {r[i] = std::min(r[2 * j - i], j + r[j] - i);}while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {r[i] += 1;}if (i + r[i] > j + r[j]) {j = i;}}return r;
}
Z 函数
/** Z函数* 2023-08-11: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63378373* 2024-04-09: https://qoj.ac/submission/384405 【模板】
**/
std::vector<int> Z(std::string s) {int n = s.size();std::vector<int> z(n + 1);z[0] = n;for (int i = 1, j = 1; i < n; i++) {z[i] = std::max(0, std::min(j + z[j] - i, z[i - j]));while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {z[i]++;}if (i + z[i] > j + z[j]) {j = i;}}return z;
}
后缀数组
/** 后缀数组（SuffixArray 旧版）* 2023-03-14: https://atcoder.jp/contests/discovery2016-qual/submissions/39727257* 2023-09-05: https://qoj.ac/submission/164483* 2024-04-09: https://qoj.ac/submission/384415 【模板】
**/
struct SuffixArray {int n;std::vector<int> sa, rk, lc;SuffixArray(const std::string &s) {n = s.length();sa.resize(n);lc.resize(n - 1);rk.resize(n);std::iota(sa.begin(), sa.end(), 0);std::sort(sa.begin(), sa.end(), [&](int a, int b) {return s[a] < s[b];});rk[sa[0]] = 0;for (int i = 1; i < n; ++i)rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);int k = 1;std::vector<int> tmp, cnt(n);tmp.reserve(n);while (rk[sa[n - 1]] < n - 1) {tmp.clear();for (int i = 0; i < k; ++i)tmp.push_back(n - k + i);for (auto i : sa)if (i >= k)tmp.push_back(i - k);std::fill(cnt.begin(), cnt.end(), 0);for (int i = 0; i < n; ++i)++cnt[rk[i]];for (int i = 1; i < n; ++i)cnt[i] += cnt[i - 1];for (int i = n - 1; i >= 0; --i)sa[--cnt[rk[tmp[i]]]] = tmp[i];std::swap(rk, tmp);rk[sa[0]] = 0;for (int i = 1; i < n; ++i)rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i - 1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);k *= 2;}for (int i = 0, j = 0; i < n; ++i) {if (rk[i] == 0) {j = 0;} else {for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1] + j]; )++j;lc[rk[i] - 1] = j;}}}
};
后缀自动机（SAM 新版）
/** 后缀自动机（SAM 新版）* 2023-05-27: https://cf.dianhsu.com/gym/104353/submission/207318083* 2023-09-25: https://qoj.ac/submission/188106* 2024-04-09: https://qoj.ac/submission/384423 【模板】* 2024-04-09: https://qoj.ac/submission/384429 【模板】
**/
struct SAM {static constexpr int ALPHABET_SIZE = 26;struct Node {int len;int link;std::array<int, ALPHABET_SIZE> next;Node() : len{}, link{}, next{} {}};std::vector<Node> t;SAM() {init();}void init() {t.assign(2, Node());t[0].next.fill(1);t[0].len = -1;}int newNode() {t.emplace_back();return t.size() - 1;}int extend(int p, int c) {if (t[p].next[c]) {int q = t[p].next[c];if (t[q].len == t[p].len + 1) {return q;}int r = newNode();t[r].len = t[p].len + 1;t[r].link = t[q].link;t[r].next = t[q].next;t[q].link = r;while (t[p].next[c] == q) {t[p].next[c] = r;p = t[p].link;}return r;}int cur = newNode();t[cur].len = t[p].len + 1;while (!t[p].next[c]) {t[p].next[c] = cur;p = t[p].link;}t[cur].link = extend(p, c);return cur;}int extend(int p, char c, char offset = 'a') {return extend(p, c - offset);}int next(int p, int x) {return t[p].next[x];}int next(int p, char c, char offset = 'a') {return next(p, c - 'a');}int link(int p) {return t[p].link;}int len(int p) {return t[p].len;}int size() {return t.size();}
};KMP
/** 前缀函数（KMP）* 2023-11-17: https://qoj.ac/submission/253754* 2024-04-09: https://qoj.ac/submission/384408 【模板】
**/
std::vector<int> kmp(std::string s) {int n = s.size();std::vector<int> f(n + 1);for (int i = 1, j = 0; i < n; i++) {while (j && s[i] != s[j]) {j = f[j];}j += (s[i] == s[j]);f[i + 1] = j;}return f;
}