学习资料：Lyndon & Runs - 洛谷专栏。yyc 讲的太好了啊，我就不抄了。
做 Lyndon 分解的 Duval 算法在 Runs 的求解中出现次数非常高，请一定记住它。
if (tl + tr >= r - l + 1) 这一行是算的刚刚好的，这里对应的 Lyndon Root 是 \([l, r)\)，然后求出 lcp，lcs 分别是 \(tl, tr\)，则这个 run 的左右端点为 \([l - tl + 1, r + tr - 1]\)，所以 \(r+tr-1-l+tl-1+1\geq 2(r-l)\) 刚好化简为 \(tl+tr\geq r-l+1\)，很不牛的。
点击查看代码
machine 在 【模板】后缀数组 SA - caijianhong - 博客园 的第一个折叠框有，就不重复放了，完整代码自寻 Submissions 2201609 - LibreOJ。
struct run {
int l, r, p;
bool operator<(const run& rhs) const {
return l != rhs.l ? l < rhs.l : r < rhs.r;
}
bool operator==(const run& rhs) const {
return l == rhs.l && r == rhs.r && p == rhs.p;
}
};
vector<run> getRuns(string s) {
int n = (int)s.size();
auto lcp = machinenew(s);
reverse(begin(s), end(s));
auto lcs = machinenew(s);
reverse(begin(s), end(s));
s += '\0';
vector<run> ans;
for (int op : {0, 1}) {
vector<int> stk;
for (int i = n - 1; i >= 0; i--) {
while (!stk.empty()) {
int u = i, v = stk.back(), len = lcp(u, v);
if ((s[u + len] < s[v + len]) == op) stk.pop_back();
else break;
}
if (!stk.empty()) {
int l = i, r = stk.back(), tr = lcp(l, r), tl = lcs(n - l - 1, n - r - 1);
if (tl + tr >= r - l + 1) ans.push_back({.l = l - tl + 1, .r = r + tr - 1, .p = r - l});
}
stk.push_back(i);
}
}
auto bg = begin(ans), ed = end(ans);
sort(bg, ed), ans.erase(unique(bg, ed), ed);
return ans;
}