我們定義一個(gè)串是Lyndon串，當(dāng)且僅當(dāng)這個(gè)串的最小后綴就是這個(gè)串本身。該命題等價(jià)于這個(gè)串是它的所有循環(huán)表示中字典序最小的。

引理 1：如果u和v都是Lyndon串并且u<v，則uv也是Lyndon串。

證明：

1、若len(u)≥len(v)

這時(shí)，u和v這兩個(gè)串在len(v) 之前就出現(xiàn)了不同的字符，所以有v>uv，又因?yàn)関是Lyndon串，所以v的所有后綴都大于v，所以u(píng)v的所有后綴都大于uv，故uv 是Lyndon串。

2、若 len(u)<len(v)

若u不是v的前綴，那么有v>uv，得證。

若u是v的前綴，那么如果v<uv，則必有v[len(u)+1:]<v（也就是各自去掉了前∣u∣個(gè)字符），矛盾。

我們定義一個(gè)串S的Lyndon分解為一個(gè)字符串序列，滿足：

，滿足是Lyndon串。

，滿足。

可以證明這種劃分存在且唯一。

存在性證明

初始令m=∣S∣并且，然后每次不斷找到并且合并為一個(gè)串。最后一定能使得所有的

唯一性證明

假設(shè)對(duì)于字符串S存在兩個(gè)Lyndon 分解：

不妨設(shè)

觀察在第二種分解中的對(duì)應(yīng)情況。假設(shè)

那么由Lyndon串的性質(zhì)可知：

矛盾。

引理2：若字符串v和字符c滿足vc是某個(gè)Lyndon串的前綴，則對(duì)于字符d>c有vd是Lyndon串。

證明：

設(shè)該Lyndon串為v+c+t。

則，也就是說。

所以。

同時(shí)因?yàn)閏>v[1]，我們有d>c>v[1]。

故v+d是一個(gè)Lyndon串。

Duval 算法

這個(gè)算法可以在O(n)時(shí)間復(fù)雜度，O(1)空間復(fù)雜度內(nèi)求出一個(gè)串的Lyndon分解。

該算法中我們僅需維護(hù)三個(gè)變量i,j,k。

維持一個(gè)循環(huán)不變式：

是固定下來的分解，也就是，是Lyndon 串且。

是沒有固定的分解，滿足t是Lyndon串，且v是t的可為空的不等于t的前綴，且有

如下圖：

當(dāng)前讀入的字符是s[k]，令j=k?∣t∣。

分三種情況討論：

當(dāng)s[k]=s[j] 時(shí)，直接k←k+1，j←j+1，周期k-j繼續(xù)保持

當(dāng)s[k]>s[j] 時(shí)，由引理2可知v+s[k] 是Lyndon串，由于Lyndon分解需要滿足，所以不斷向前合并，最終整個(gè)形成了一個(gè)新的Lyndon串。

當(dāng)s[k]<s[j] 時(shí)，的分解被固定下來，算法從v的開頭處重新開始。

復(fù)雜度分析：i只會(huì)單調(diào)往右移動(dòng)，同時(shí)k每次移動(dòng)的距離不會(huì)超過i移動(dòng)的距離，所以時(shí)間復(fù)雜度是O(n)的。

代碼如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[5000005];
int n,ans;
int main()
{
    scanf("%s",s+1);
    n=(int)strlen(s+1);
    for(int i=1;i<=n;)
    {
        int j=i,k=i+1;//初始化
        while(k<=n&&s[j]<=s[k])
        {
            if(s[j]<s[k])j=i;//合并為一整個(gè)
            else j++;//保持循環(huán)不變式
            k++;
        }
        while(i<=j)//從v的開頭重新開始
        {
            ans^=i+k-j-1;
            i+=k-j;
        }
    }
    printf("%d\n",ans);
    return 0;
}