#4635. 模板.Lyndon 分解

模板.Lyndon 分解

【模板】Lyndon 分解

题目描述

这是一道模板题。

读入一个由小写英文字母组成的字符串 ss ,请把这个字符串分成若干部分 s=s1s2s3sms=s_1s_2s_3\cdots s_m,使得每个 sis_i 都是 Lyndon Word\text{Lyndon Word},且 1i<m:sisi+1\forall 1\le i<m:s_i\ge s_{i+1}。输出 s1s_1sms_m 这些串长度的右端点的位置。位置编号为 11nn

一个字符串 ss 是一个 Lyndon Word\text{Lyndon Word},当且仅当 ss 是其所有后缀中最小的字符串。

为了减小输出量,你只需要输出所有右端点的异或和。

输入格式

一行一个长度为 nn 的仅包含小写英文字母的字符串 ss

输出格式

一行一个整数,表示所有右端点的异或和。

样例 #1

样例输入 #1

ababa

样例输出 #1

3

样例 #2

样例输入 #2

bbababaabaaabaaaab

样例输出 #2

23

提示

第一组样例的答案为 2 4 5

第二组样例的答案为 1 2 4 6 9 13 18

  • 对于 20%20\% 的数据,保证 1n10001\le n\le 1000
  • 对于 100%100\% 的数据,保证 1n5×106+11\le n\le 5\times 10^6+1