【字符串】Lyndon分解

Lyndon串：当且仅当字符串 \(s\) 的字典序严格小于其所有后缀的字典序时，字符串 \(s\) 是Lyndon串。当且仅当字符串 \(s\) 的字典序严格小于其所有非平凡循环同构串的字典序时，字符串 \(s\) 是Lyndon串。

Lyndon分解：字符串 \(s\) 的Lyndon分解为 \(s=w_1+w_2+\cdots +w_n\) ，其中所有的 \(w_i\) 都为Lyndon串，并且他们的字典序按非严格单调递减排序，即 \(w_1\geq w_2\geq \cdots \geq w_n\) 。这样的分解存在且唯一。

Duval算法：时间复杂度 \(O(n)\)

vector<string> duval(string const& s) {
    vector<string> fac;
    int n = s.size(), i = 0;
    while (i < n) {
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            (s[k] < s[j]) ? (k = i) : ++k;
            ++j;
        }
        while (i <= k) {
            fac.push_back(s.substr(i, j - k));
            i += j - k;
        }
    }
    return fac;
}

最小表示法：寻找字符串 \(s\) 的最小循环移位同构串。对字符串 \(s+s\) Lyndon分解，找到唯一的那个跨越两个字符串交界的Lyndon串，输出这个Lyndon串的开头位置在原串对应位置的前n个字符。

（好像这东西没什么用啊，后缀数组不比这简单？）