西江月·证明

即得易见平凡，仿照上例显然。

留作习题答案略，读者自证不难。

反之亦然同理，推论自然成立。

略去过程Q.E.D.，由上可知证毕。

后缀数组

就是后缀数组。

主要由两个数组组成，$sa[i]$ 表示为把所有后缀按照字典序排序之后的第 $i$ 小的后缀编号，而 $rk[i]$ 表示编号为 $i$ 的后缀的排名。显然，有 $sa[rk[i]]=rk[sa[i]]=i$。

我们可以在 $O(log\ n)$ 的时间复杂度内求出来。

我们这里会利用倍增的思想去实现。

这里就用一个经典老图来描述一下过程

本质上也就是一个双关键字排序的过程。

如果我们是用sort排序的话就会退化成$O(nlog^2n)$，为了更快速地求出来，我们需要用到一种 $o(n)$ 排序，基数排序优化即可。

const int Maxn = 1000010;
int n;
char s[Maxn];
int sa[Maxn], rk[Maxn], oldrk[Maxn << 1];
int id[Maxn], px[Maxn], cnt[Maxn];
// px[i] = rk[id[i]]
inline bool cmp(int x, int y, int w)
{
    return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
inline void work()
{
    int i, m = 300, p, w;

    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (i = 1; i <= n; ++i)
        ++cnt[rk[i] = s[i]];
    for (i = 1; i <= m; ++i)
        cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i)
        sa[cnt[rk[i]]--] = i;

    for (w = 1;; w <<= 1, m = p)
    {
        for (p = 0, i = n; i > n - w; --i)
            id[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > w)
                id[++p] = sa[i] - w;
        memset(cnt, 0, sizeof(cnt));
        for (i = 1; i <= n; ++i)
            ++cnt[px[i] = rk[id[i]]];
        for (i = 1; i <= m; ++i)
            cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i)
            sa[cnt[px[i]]--] = id[i];
        memcpy(oldrk, rk, sizeof(rk));
        for (p = 0, i = 1; i <= n; ++i)
            rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
        if (p == n)
        {
            for (int i = 1; i <= n; ++i)
                sa[rk[i]] = i;
            break;
        }
    }

    for (i = 1; i <= n; ++i)
        printf("%d ", sa[i]);
}
int main()
{
    work();
    return 0;
}

当然还有更牛逼的 $O(n)$ 求法，我们在这里不涉及。

关于应用的话，比如说在字符串中快速找到子串，显然的一个性质就是若是子串，必定是原串的某些后缀中的前缀。

我们就可以利用这个性质来去二分地查找位置，做到$O(|S|log\ |T|)$的复杂度。

并且，我们在求出了后缀数组之后可以利用它的性质求出一些其他有用的数组来帮助我们维护一些奇怪的东西。

height数组

这里我们定义 $ height[i]=lcp(sa[i],sa[i-1]) $，也就是说第 $i$ 名的后缀与它前一名的后缀的最长公共前缀长度。其中 $ height[1]=0 $。

那么咋求出来？只需要一个定理： $height[rk[i]] \ge height[rk[i-1]]-1 $。

那么我们就可以 $O(n)$ 暴力地求出来了不是吗？

for(int i=1,k=0;i<=n;i++)
{
	if(rk[i])
	{
		if(k)	
			k--;
		while(s[i+k]==s[sa[rk[i]-1]+k)
			k++;
		height[rk[i]]=k;
	}
}

既然我们求出来了这个数组，它就一定有它特别的用处，即应用。

可以用来求LCP：

显然 $lcp(sa[i],sa[j])=min(height[i+1...j])$，那么我们就把LCP变成了RMQ问题去求解。

可以用来比较同一字符串中两子串的大小关系：

假设我们需要比较 $A=S[a..b]$，$B=S[c..d]$，如果有 $lcp(a,c)
\ge min(|A|,|B|) $，那么 $A<B \Leftrightarrow |A|<|B| $，否则的话， $A<B \Leftrightarrow rk[a]<rk[c]$。

也可以用来求不同的子串的数目：

子串也就是后缀的前缀。那么我们可以美剧每一个后缀，计算它的前缀总数量，最后在减去重复的。
按照后缀排序的顺序去枚举后缀，那么每次新增的子串就是除了与上一个后缀的LCP剩下的前缀且这些前缀一定没有被计算过，否则就会破坏LCP与height之间的关系性质。所以答案就是 $n(n+1)/2-\sum\limits_{i=2}^{n}height[i] $。

可以用来求出现至少k次的子串的最大长度：

也就是后缀排序中至少有连续$k$个连续的后缀的LCP是这个串。所以我们求助每相邻 $k-1$ 个$height$的最小值，再求这些最小值中的最大值就是答案。可以用单调队列解决，时间复杂度是 $o(n)$ 的。

可以用来判断是否有某文本串不重叠地出现了至少两次：

可以直接二分目标地的长度，并将 $height$ 数组划分为若干个连续的LCP大于等于$s$的小块，然后去对每一个块求其中出现数中最大值和最小值的下表，如果两个下表之差满足条件，那么就一定会有满足条件的串。

除此之外，它还可以解决有关连续的若干个相同子串的问题，详情可见 [NOI2016] 优秀的拆分。

关于这题，显然AABB是由两个形如AA的串拼起来的，所以我们考虑去维护两个数组$a$和$b$，其中$a[i]$用来表示以$i$结尾有多少个形如AA的串，而 $b[i]$ 则表示以$i$开头有多少个形如AA的串。

那么最终解为$\sum\limits_{i=1}^{n-1}a[i]b[i+1] $。

我们就只需要考虑怎么把这两个数组求出来即可。

显然可以 $o(n^2)$ 地用哈希求出来，也就是对于每一个 $i$ 都用 $j$ 扫一遍去哈希判断有几个AA串。

我们考虑去枚举一个 $len$ ，然后对于每一个节点去求出来他是否是一个 $len*2$ 地一个AA串地开头或者结尾。

我们每隔着一个 $Len$ 放一个监视点，那么每一个长度满足要求的串都会至少经过两个相邻的点。所以我们就可以直接转换为每两个相邻的点之间会对 $a,b$ 产生什么贡献。

那么先求出来这对相邻点所代表前缀的最长公共后缀 $LCS$ 与其所代表的后缀的最长公共前缀 $LCP$ ，方便我们进行后面的判断。那么如果 $ LCP+LCS<Len $ 的话就不合法了。也就是说中间两段的$LCP$与$LCS$会有交集，但是我们这个A串的落脚点位于中间长度为 $LCP+LCS-Len+1$ 的交集处都是合法的。

所以我们就可以直接差分了，复杂度为 $O(nlog\ n)$。

代码就不放了因为我没写。

后缀自动机

可以在 $O(n)$ 的时间与空间复杂度内解决很多字符串相关问题的有力数据结构。

它以高度压缩的形式存在，是一张有向无环图的形式，包含了关于字符串 $s$的所有子串的信息。任意一个从初始状态 $t_0$ 开始的路径，如果我们把转移路径上的标号写下来，都会形成一个 $s$ 的子串，或者也可以说每个 $s$ 的子串都对应了一条从 $t_9$ 开始的路径。

那么我们可以称任意一条路径对应了它标号所构成的字符串。由于到达某个状态的路径不止一条，我们说一个状态对应了一些字符串的集合，而这个集合的每个元素会单独对应这些路径。

定义说完了，构建可以看OI-Wiki

后缀平衡树

一种用来维护字符串后缀的数据结构，是把所有后缀按照字典序排序后构建出来的平衡树。

构造：

我们先尝试着离线构造一棵这样的树。

设我们有字符串 $abababc$ ，它的所有后缀按照字典序排列后我们也可以很容易的得出：$abababc$ ，
+$ababc$，$abc$，$bababc$，$babc$，$bc$，$c$。

然后对着一个序列怎么给他弄成平衡树？替罪羊树很好的告诉了我们答案，二分把它拎起来就行。

但是我们这种做法还是需要提前求出来后缀数组，时间复杂度为 $O(n)\ or\ O(log\ n)$，取决于我们计算后缀数组的算法。

那么我们再考虑在线构造。

那就把后缀一个一个地插入平衡树即可。

我们遍历到每一个节点的时候，用即将插入的后缀 $x$ 和此节点所代表的后缀 $y$
按照字典序去比较一下，如果 $x>y$ ，向右插入即可。又因为每一个后缀都不一样，所以一定不会出现重复的情况。

我们这里用Treap作为基本模板。

然后我去网上偷了图，我们在这里模拟一下 $abababc$ 建立后缀平衡树的过程。

1.

2.

3.


4.

5.

6.


7.


其中有两步的就是插入后不满足性质，我们用旋转去维护平衡树的性质。

与之相对应的，它也支持删除操作。再整一个例子，我们把它的后缀一个一个删除。

原图:

1.删 $abababc$

2.删 $bababc$

然后它就一分为二了，此时我们可以用 FHQ的merge去合并，也可以直接写无旋Treap的分类讨论。

完事之后就这样:

然后接着重复删除操作。

3.删 $ababc$

4.删 $babc$

5.删 $abc$

6.删 $bc$

剩下个 $c$，删完之后就是空的。

那么后缀平衡树就可以动态地插入、删除一个后缀辣！

但是我们操作的是后缀，所以我们只是可以在一个字符串前插入或者删除一个字符。与之相对的，后缀自动机是在后面插入一个字符。

当然，它本质上还是个平衡树，你会写平衡树就会写，所以并不难掌握。

我们由普通的平衡树插入入手，给他做一些修改。

我们普通平衡树一般需要去维护 $size,cnt,val,key$几个东西来维护树的形态与性质，但是在后缀平衡树里，$val$的意义并不明确。

但是我们只关心字典序大小来比较即可，那么我们可以把每个点的编号设置为当前后缀开始的位置，比如节点 $1$ 可以代表从 $1$ 开始的后缀。那么由于后缀的唯一性和长度的单调性，我们就可以直接比较啦。

那么代码可以这样写：

inline void ins(int &i, int p) //这里的i为当前访问节点编号，而p为当前插入后缀的开始节点
{
    if (!i)
    {
        trp[p].key = rand();
        trp[p].size = 1;
        trp[p].cnt = 1;
        i = p; //节点编号为后缀开始的位置
        return;
    }
    if (comp(i, p) > 0)
    { //这里是比较字典序
        ins(trp[i].ls, p);
        up(i);
        if (trp[i].key > trp[trp[i].ls].key)
            zig(i);
    }
    else if (comp(i, p) < 0)
    {
        ins(trp[i].rs, pos);
        pushup(i);
        if (trp[i].key > trp[trp[i].rs].key)
            zag(i);
    }
    //由于字典序不可能相等，我们也就不用考虑最后一种相等的情况啦
}

那么我们还剩下个问题：怎么去写两个后缀的比较函数捏？

我们当然可以暴力比较，但是很劣。

我们想要的是 $O(1)$ 的优秀复杂度，所以我们要从插入的后缀去入手：

现在我们的任务是在已经插入完毕的字符串 $S$ 前面再插入一个字符 $x$ ，也就是插入新的后缀为 $xS$，那么$S$这一后缀在平衡树中位置我们是已知的，并且大小关系也已经确定，我们可以从这一点出发去利用它的性质。

我们重新定义每个点的权值 $val$ 用以比较。正常情况下我们是如何判断字符大小关系的？我们模拟一下暴力比较，首先比较第一个字符，如果不同的话我们就已经得知两个后缀之间的大小关系了。如果不相同的话，那么去掉首字符之后的后缀我们也已经在树上出现过了，那么我们就可以直接通过判断 $val$ 去比较了。也就是说，我们插入的后缀本身就是有序插入，相当于每次插入一个新的首字符在前。

大概代码实现是这样的

inline int comp(int x, int y)
{
    if (s[x] > s[y] or s[x] == s[y] and trp[x + 1].val > trp[y + 1].val)
        return 1;
    else if (s[x] == s[y] and trp[x + 1].val == trp[y + 1].val)
        return 0;
    else
        return -1;
}

那么现在我们解决了一个问题，但是又创造出了一个新问题： $val$ 如何确定？

我们当然可以直接前驱和后继取个平均值来算，但是这样会有精度问题。也就是说如果我们插入后缀是单调上升的，你构造出来的树就会是偏心的。

那么我们基于这个东西优化一下。我们发现上面的方法中会使权值构造出来一棵并不平衡的树，考虑利用它的性质来完成我们构建真正的平衡树。

就像线段树一样，传 $l，r$ 两个参数，那么权值就定义为 $(l+r)>>1$ 那么走向左子树的话就会变成 $l, ((l+r)>>1)-1$ ，右子树就成了 $(l+r)>>1，r$ 。

但是每一次旋转会改变权值，不是吗？

那么我们可以去利用“重量平衡树”的方法去平衡。也就是说，在进行了插入或者删除操作之后，为了保证树的平衡而重构子树大小为均摊或者说期望 $O(log\ n)$。

那么，我们每一次插入都需要用 $O(log\ n)$ 时间去找到我们需要插入的位置，再用 $O(log\ n)$ 去重构子树。那么就是多了个小常数罢了

那么代码也就可以写出来了

inline void get_val(int p, long long l, long long r)
{ //重构
    if (!p)
        return;
    trp[p].val = (l + r) >> 1;
    get_val(trp[p].ls, l, trp[p].val - 1);
    get_val(trp[p].rs, trp[p].val + 1, r);
}
inline void zig(int &p, long long l, long long r)
{
    int q = trp[p].ls;
    trp[p].ls = trp[q].rs;
    trp[q].rs = p;
    up(p), up(q);
    get_val(q, l, r);
    p = q;
}
inline void zag(int &p, long long l, long long r)
{
    int q = trp[p].rson;
    trp[p].rson = trp[q].lson;
    trp[q].lson = p;
    pushup(p);
    pushup(q);
    get_val(q, l, r);
    p = q;
}
//左右旋。不想传l和r的可以在外面get_val
void ins(int &i, int p, long long l, long long r)
{
    if (!i)
    {
        trp[p].key = rand();
        trp[p].val = (l + r) >> 1;
        trp[p].size = 1;
        trp[p].cnt = 1;
        i = p return;
    }
    if (comp(i, p) > 0)
    {
        ins(trp[i].ls, pos, l, trp[i].val - 1);
        up(i);
        if (trp[i].key > trp[trp[i].ls].key)
            zig(i, l, r);
    }
    else if (comp(i, p) < 0)
    {
        ins(trp[i].rs, p, trp[i].val + 1, r);
        up(i);
        if (trp[i].key > trp[trp[i].rs].key)
            zag(i, l, r);
    }
    return;
}

删除同理，这里用FHQ的做法去合并，就不用分类讨论了。那么合并后只需要重构即可。

inilne int merge(int x, int y)
{
    if (!x || !y)
        return x | y;
    if (trp[x].key < trp[y].key)
    {
        trp[x].rs = merge(trp[x].rs, y);
        up(x);
        return x;
    }
    else
    {
        trp[y].ls = merge(x, trp[y].ls);
        up(y);
        return y;
    }
}
void del(int &i, int p, long long l, long long r)
{
    if (!i)
        return;
    if (comp(i, p) == 0)
    {
        if (trp[i].cnt > 1)
            trp[i].cnt--;
        else
            i = merge(trp[i].ls, trp[i].rs), get_val(i, l, r);
        pushup(i);
        return;
    }
    if (comp(i, p) > 0)
        del(trp[i].ls, p, l, trp[i].val - 1);
    else
        del(trp[i].rs, p, trp[i].val + 1, r);
    up(i);
    return;
}

那么后缀平衡树的插入与删除我们就知道了。

怎么让它做后缀数组的活呢？

你建立完之后你会发现dfs一遍就可以求出来$SA$里的 $sa,rk$ 两个数组了。

还是有代码

int cnt;
inline void dfs(int i)
{
    if (!i)
        return;
    dfs(trp[i].ls);
    sa[++cnt] = i, rs[i] = cnt;
    dfs(rtp[i].rs);
    return;
}

总的来说后缀平衡树就是 $SA$ + 平衡树，并且多了一个可添加字符的操作，这是 $SA$不支持的。而对于后缀自动机来说，它又多支持了一个删除的操作。

它的代码相对来说更长，但是由于有了平衡树的前身，它并不难懂也并不难写。

没了。

回文自动机（回文树）

这俩是一个东西=_=虽然我以前一直不知道

是可以在$O(n)$时间内求出来一个字符串的所有回文子串的算法。

自动机的结构都差不多，回文自动机也是由转移边与$fail$指针构成的，而每个节点都表示一个回文子串。更准确地说，是在它的父节点各加上一个儿子字符构成的串。

又由于回文串的长度存在奇数和偶数两种，那么我们肯定不能直接建在一棵树上，所以我们考虑建两棵树来分别存储这两种不同的回文串。

那么我们就考虑去记录下来两棵树的两个根，也就是奇根与偶根。那么我们一般限定偶根编号为$0$，所代表回文串的长度为$0$，其$fail$边指向奇根。而奇根的编号为$1$，所代表回文串长度为$1$，其$fail$边指向自身。

那么我们再说说$fail$指针。

先说一下结论，一个点的$fail$，指向的是这个节点的最长回文后缀。

我们再加入一个新的字符的时候，我们需要从当前的节点不断地去跳$fail$指针，直到某一个节点的回文串两侧都可以拓展一个待添加的字符。那么我们就看这个点有没有儿子，有的话就直接走子节点的路径，没有的话就新建一个节点，我们给他造一个儿子。

那么新建节点的长度一定是等于这个节点的长度加上$2$，所以怎么求这个$fail$指针呢？我们可以考虑一个节点的最长回文后缀。

一个新节点肯定是在它父节点的某一个回文后缀的两侧各拓展一个字符所得到的，所以新建节点后，我们可以从它父亲的$fail$指针开始跳，直到第一个两侧能够拓展当前这个字符的节点为止，这个节点的儿子就是我们新建节点的最长回文后缀。

我们在这里再特殊的看一下两个根的$fail$指针。由于奇根子节点所表示的回文长度为$1$，也就是这个字符本身，那么奇根相当于是可以向两侧任意拓展字符，所以我们会把偶根的$fail$指向奇根。

而如果跳到的是奇根，那么肯定是可以向两侧拓展的，所以奇根的$fail$指针不必存在，赋成什么值都一样。

那么就可以直接看代码啦：

#define Maxn 2000010
struct node
{
    int fail, num, lens; //分别记录了fail指针，当前回文子串出现次数，与当前子串的长度
    int ch[26];
} t[Maxn];
int n, len, lst, cnt, s[Maxn];
char c[Maxn];
inline void init()
{
    t[0].lens = 0, t[1].lens = -1;
    t[0].fail = 1, t[1].fail = 0;
    lst = 0, cnt = 1;
    return;
}
inline int gtfail(int i)
{
    while (s[n - t[i].lens - 1] != s[n])
        i = t[i].fail;
    return i;
}
inline void ins()
{
    int i = gtfail(lst);
    if (!t[i].ch[s[n]])
    {
        t[++cnt].lens = t[i].lens + 2;
        int v = gtfail(t[i].fail);
        t[cnt].fail = t[v].ch[s[n]];
        t[cnt].num = t[t[cnt].fail].num + 1;
        t[i].ch[s[n]] = cnt;
    }
    lst = t[i].ch[s[n]];
}
int k;
inline void work()
{
    init();
    scanf("%s", c + 1);
    len = strlen(c + 1);
    s[0] = 26;
    for (n = 1; n <= len; n++)
    {
        c[n] = (c[n] - 97 + k) % 26 + 97;
        s[n] = c[n] - 'a';
        ins();
        printf("%d ", t[lst].num);
        k = t[lst].num;
    }

    return;
}
int main(void)
{
    work();
    return 0;
}

那么这就是回文自动机的板子啦

最小表示法

是求出字符串的最小表示的算法。

什么是最小表示？即为一个字符串首尾拼接后你随意找一个点断开，要求断开之后形成的字符串的字典序最小。

我们可以在 $O(n)$ 的时间内解决这个问题。

首先把这个字符串复制一遍放在原串的后面。

我们一开始搞两个指针 $i$ 和 $j$ ，初始的时候分别指向 $s[0]$ 与 $s[1]$ 然后我们规定在任意时刻这两个指针都不可以指向相同的位置。那么我们设一个匹配长度 $k=0$ 开始，我们去检查 $s[i+k]$ 与 $s[j+k]$ 是否相等，如果相等的话 $k++$，直到找到第一个不相同的字符。

如果整个字符串的长度都没有找到不相等的位置，那么证明整个字符串都是相等的字符，那么那个位置就是最小表示的位置，直接返回即可。

显然，全过程中 $s[i+k]$ 与 $s[j+k]$ 的大小关系只有三种：

1.当 $s[i+k]>s[j+k]$ 时，显然 $s[i] - s[i+k-1]$ 都不可能是最小表示的前缀，那么 $i$ 指向 $i+k+1$ 处即可。

2.当 $s[i+k]<s[j+k]$ 时，同理，直接把 $j$ 指向 $j+k+1$。

3.当 $s[i+k]=s[j+k]$ 时，直接 $k++$。

那么如果改变指向后 $i=j$ 那么我们直接把正在变化的指针再向后值一位，直到
$i,j$ 把整个字符串都检查一遍，返回两者之间小于字符串长度的一个。

也就是如果 $k=len$（其中 $len$ 为字符串原长），我们返回 $min(i,j)$。

const int Maxn = 3e5 + 10;
int n;
int a[Maxn * 2];
int ansx;
int i, j = 1, k;
inline void work()
{
    n = read();
    for (register int i = 0; i < n; i++)
        a[i] = read();
    while (i < n and j < n and k < n)
    {
        if (a[(i + k) % n] == a[(j + k) % n])
            k++;
        else
        {
            if (a[(i + k) % n] > a[(j + k) % n])
                i += k + 1;
            else
                j += k + 1;
            if (i == j)
                i++;
            k = 0;
        }
    }
    ansx = min(i, j);
    for (register int i = 0; i < n; i++)
        printf("%d ", a[(i + ansx) % n]);
    return;
}

这东西用处的话。。。主要还是用它的性质去做一些最优性选择之类的，当然你也可以来判断两个字符串是不是本质相同。

当然了你也可以直接去用SA来做捏。

Lyndon分解

冷门。

我们先下个定义：Lyndon串，我们定义为字符串本身就是所有后缀中字典序最小的。

而Lyndon分解，就是把字符串按照顺序不重叠地划分为 $m$ 个Lyndon串，并且保证 $s_i\ge s_{i+1}$。（是按照字典序排序）

那么其实Lyndon分解可以直接利用后缀数组求解：首先，$s_m$的起点肯定是 $sa[1]$，然后接着考虑 $s_{m-1}+s_m$ 是除了 $s_m$ 的后缀中字典序最小的后缀，我们可以用一个数组去记录 $rk=i$ 的后缀是否已经被包含了，那么我们每次向后找到第一个不被包含的 $rk$ ，把它设置为新增的 Lyndon 串的开头即可。

那么这个做法的复杂度是跟后缀数组复杂度挂钩的。

重新考虑一种做法。

给出引理：1. 如果$a$和$b$都是Lyndon串，并且 $ a<b $ ，那么 $ab$ 也是一个Lyndon串。

2.如果字符串$a$与字符$c$满足$ac$是一个lyndon串的前缀，那么对于大于$c$的字符$d$，肯定有$ad$是Lyndon串。

证明的话我可能口胡，也可能由于一些原因而导致不证明，我们现在就把他当作一个前提条件。

Duval算法

可以在 $O(n)$ 的时间复杂度内求出来一个字符串的Lyndon分解。我们需要维护三个指针： $i,j,k$。其中 $i$ 的含义为接下来开始划分的位置，也就是说 $[1,i-1]$ 之内的区间已经划分完毕。

那么就去维护一个循环不变式，也就是说保持这个式子在循环的过程中始终为真。

为 $ s[1,i-1]=s_1s_2s_3…sg, \forall l \in [1,g],s_l \in Lyndon $ 串且 $sl>s{l+1}$。

$ s[i,k-1] = t^h + v(h>1) $ 为不固定的分解，并且满足 $v$ 为 $t$ 的真子前缀。并且满足 $ s_g>s[i,k-1] $。

大体的关系就是这样子：

我们当前读入的字符为 $s[k]$ ，而令 $j=k-|t|$，然后分类讨论。

$ s[k]=s[j] $，那么 $ k++,j++ $

$ s[k]>s[j] $，由引理2可得 $ s[k]+v $为Lyndon串，那么又由于Lyndon分解有字典序限制，那么我们就不断向前合并，最终会得到 $ t^h+v+s[k] $ 为一个新的符合条件的Lyndon串。

$ s[k]<s[j]> , t^h $ 的分解就被固定下来，而算法就会直接从 $v$ 的开头处重新开始运行。

最终我们可以得到一个 $ O(n) $的做法。

#include <bits/stdc++.h>
using namespace std;
#define Maxn 100010 * 50
int n, ansx;
char s[Maxn];
inline void work()
{
    scanf("%s", s + 1), n = strlen(s + 1);
    for (int i = 1; i <= n;)
    {
        int j = i, k = i + 1;
        while (k <= n and s[j] <= s[k])
            s[j] < s[k] ? j = i : j++, k++;
        while (i <= j)
            ansx ^= i + k - j - 1, i += k - j;
    }
    printf("%d", ansx);
    return;
}
int main(void)
{
    work();
    return 0;
}

没了。

Main-Lorentz 算法

我们称形如一个字符串复制一遍之后放在它本身后边形成的新字符串为重串。

我们的目标是找到给定字符串中的所有重串，或者，我们解决一个更简单的问题：我们找到一个字符串中的任意一个重串或者最长的一个重串。

我们在开始之前首先界定一下，$\bar{S}$ 为字符串 $S$ 取反，即反转过来。而下文中所有字符串下标都从0开始。

重串个数

一个字符串$s$可能会有 $ |S|^2 $ 个重串，但是这并不影响我们在 $ O(n\ log\ n) $的复杂度下计算出重串的数量。因为我们是通过某种压缩的形式来表示一个重串，是的我们可以把多个重串压缩为一个。

这里还会有一些关于重串数量的结论：

若是一个重串的原串并不是重串，那么我们称这个串为本原重串，并且可以证明的是，本源重串最多只有 $nlogn$ 个。

若是我们把一个重串用一个三元组 $ (i,p,r) $ 进行压缩，且其中 $i$ 为重串的起始位置， $p$ 为重串中某个循环节的长度， $r$为这个循环节的重复次数，那么字符串中的所有重串都可以被 $nlogn$个三元组表示。

我们发现斐波那契字符串具有高度周期性。对于一个长度为 $n_i$ 的斐波那契字符串 $s_i$ ，使用三元组压缩之后也会有 $ n_ilogn_i $ 个三元组，与其本原重串数量相同。

Main-Lorentz 算法

核心是分治。

这个算法是把字符串划分为左右两个部分，首先计算完全处于字符串左部或者右部的重串数量，然后再计算起始位置在左部，终止部分在右部的重串数量。这个算法的关键点在于求交叉重串的数量，我们在下面去探讨。

计算交叉重串

我们记一个字符除按左部为$u$，右部为$v$，那么$s=u+v$，并且$u,v$长度都约为$s$的一半。如果 $s[i...j]$ 为重串，那么我们规定中间字符为 $ s[(i+j+1)/2] $.如果中间字符在 $u$ 中则称这个重串左偏，反之称右偏。

那么我们接下来考虑如何找到所有的左偏重串。

我们会记录左边重串长度为 $2l$，那么考虑该重串中第一个落入 $v$的字符（$ s[|u|] $），这个字符肯定是与 $u$ 中某个字符 $u[p]$ 相同。

那么就把 $p$ 固定，然后去找到所有符合条件的重串。比如说对于一个字符串 $cac\ ada$，固定住 $p=1$ ，然后我们可以发现 $caca$ 是一个符合要求的重串。

那么我们一旦固定住了 $p$，同时也就固定住了 $l$ 的范围。一旦知道如何去找所有的重串我们就可以直接枚举 $p$ 的值，然后去找到所有符合条件的重串。

左偏判定

即使固定住了 $p$，仍然可能会有很多满足条件的串，我们现在探讨的就是不重不漏地把它们找出来。

我们记录 $len_1$ 为一个重串的首字符到 $s[p-1]$ 所组成的子串的长度，记录 $len_2$ 为 $s[p]$ 到该串左边原串的末尾字符所组成的字符串长度。

所以我们可以给出某个长度为 $ 2l=2(l_1+l_2)=2(|u|-p) $ 的子串为重串的充要条件：

我们设 $ k_1 $ 为满足 $ u[p-k_1,…p-1]=u[|u|-k_1…|u|-1] $ 的最大整数，而 $ k_2 $ 为满足 $ u[p…p+ k_2-1]=v[0…k_2-1] $ 的最大整数，那么对于任意满足 $ l_1\le k_1,l_2\le k_2 $ 的二元组来说，我们都可以恰好找到一个与之对应的重串。

所以我们考虑怎么计算 $k_1,k_2$ 即可。

$k_1$ 只需计算 $\bar{u}$ 的Z函数，而计算 $k_2$ 也只需要计算 $ v+’’+u $ 的Z函数，而’'所代表的是 $u,v$ 中均不可能存在的字符。

右偏重串就和求左偏重串的方法几乎一致了，这里感兴趣的可以看OI-Wiki，不再阐述。

实现的话如果你只想找一个重串，时间复杂度为$O(n\ log\ n)$，如果求所有的重串的话为 $O(n^2)$ 的复杂度。代码实现如下：

vector<int> z_function(string const &s)
{
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++)
    {
        if (i <= r)
            z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;
        if (i + z[i] - 1 > r)
        {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

int get_z(vector<int> const &z, int i)
{
    if (0 <= i && i < (int)z.size())
        return z[i];
    else
        return 0;
}

vector<pair<int, int>> repetitions;

void convert_to_repetitions(int shift, bool left, int cntr, int l, int k1, int k2)
{
    for (int l1 = max(1, l - k2); l1 <= min(l, k1); l1++)
    {
        if (left && l1 == l)
            break;
        int l2 = l - l1;
        int pos = shift + (left ? cntr - l1 : cntr - l - l1 + 1);
        repetitions.emplace_back(pos, pos + 2 * l - 1);
    }
}

void find_repetitions(string s, int shift = 0)
{
    int n = s.size();
    if (n == 1)
        return;

    int nu = n / 2;
    int nv = n - nu;
    string u = s.substr(0, nu);
    string v = s.substr(nu);
    string ru(u.rbegin(), u.rend());
    string rv(v.rbegin(), v.rend());

    find_repetitions(u, shift);
    find_repetitions(v, shift + nu);

    vector<int> z1 = z_function(ru);
    vector<int> z2 = z_function(v + '#' + u);
    vector<int> z3 = z_function(ru + '#' + rv);
    vector<int> z4 = z_function(v);

    for (int cntr = 0; cntr < n; cntr++)
    {
        int l, k1, k2;
        if (cntr < nu)
        {
            l = nu - cntr;
            k1 = get_z(z1, nu - cntr);
            k2 = get_z(z2, nv + 1 + cntr);
        }
        else
        {
            l = cntr - nu + 1;
            k1 = get_z(z3, nu + 1 + nv - 1 - (cntr - nu));
            k2 = get_z(z4, (cntr - nu) + 1);
        }
        if (k1 + k2 >= l)
            convert_to_repetitions(shift, cntr < nu, cntr, l, k1, k2);
    }
}