字符串备忘录

简要且不一定加以证明地记录某些字符串理论中的一些结论。
翻译：不是给你看的，是给我自己看的（

Lyndon 分解 - Duval 算法

Lyndon 分解的定义略。

算法的流程是维护三个指针 i,j,k 形成的循环不变式：

• s[1…i−1]=s1s2…sg 是已经确定的分解。

• s[i…k−1]=th+v 是待定的分解，其中 t 是一个 Lyndon Word，h>1，v 是 t 的真前缀，且 sg≥s[i…k−1]。

同时维护 j=k−|t|，考虑 s[k]，分类讨论

• s[j]=s[k]，则周期继续维持，j←j+1,k←k+1。

• s[j]<s[k]，v+s[k] 为 Lyndon Word，将 th+v+s[k] 合并为一个新的 Lyndon Word t，即令 j←i。

• s[j]>s[k]，确定 th 的分解，算法从 v 的开头继续。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 5e6;
int n;
char s[N + 5];
int ans;
int main()
{
    scanf("%s",s + 1),n = strlen(s + 1);
    for(register int i = 1,j,k;i <= n;)
    {
        j = i,k = i + 1;
        for(;k <= n && s[j] <= s[k];++k)
            s[j] < s[k] ? (j = i) : ++j;
        for(;i <= j;i += k - j)
            ans ^= i + k - j - 1;
    }
    printf("%d\n",ans);
}

Runs

The Runs Theorem

ρ(n)<n,σ(n)<3n−3

求 Runs

令 <0,<1 为 Σ 上两种相反的全序关系，类似地定义到 Σ∗ 上的字典序关系。
对于 ℓ∈{0,1}，令 ¯ℓ=1−ℓ。

简要概括：对 ℓ∈{0,1} 求出每个后缀在 <ℓ 意义下的最长 Lyndon Word 前缀。枚举一个作为某个 Lyndon Root 求前后最长可扩展的长度，判断加起来是否不小于 p。去重。

代码：

#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 1e6;
const int P = 131;
const int mod = 998244353;
int n;
char s[N + 5];
int pw[N + 5],hs[N + 5];
inline int Hash(int l,int r)
{
    return (hs[r] - (long long)hs[l - 1] * pw[r - l + 1] % mod + mod) % mod;
}
inline int LCP(int a,int b)
{
    int l = 1,r = min(n - a + 1,n - b + 1),mid,ret = 0;
    while(l <= r)
        mid = l + r >> 1,
        Hash(a,a + mid - 1) == Hash(b,b + mid - 1) ? (ret = mid,l = mid + 1) : (r = mid - 1);
    return ret;
}
inline int LCS(int a,int b)
{
    int l = 1,r = min(a,b),mid,ret = 0;
    while(l <= r)
        mid = l + r >> 1,
        Hash(a - mid + 1,a) == Hash(b - mid + 1,b) ? (ret = mid,l = mid + 1) : (r = mid - 1);
    return ret;
}
int ly[N + 5];
pair<int,int> st[N + 5];
int top;
inline void lyndon(int op)
{
    top = 0;
    for(register int i = n,j;i;--i)
    {
        j = i;
        for(register int lcp;top;--top)
        {
            lcp = LCP(i,st[top].first);
            if((s[i + lcp] >= s[st[top].first + lcp]) ^ op)
                break;
            j = st[top].second;
        }
        st[++top] = make_pair(i,ly[i] = j);
    }
}
struct Run
{
    int l,r,p;
    inline bool operator<(const Run &o) const
    {
        return l ^ o.l ? l < o.l : r < o.r;
    }
    inline bool operator==(const Run &o) const
    {
        return l == o.l && r == o.r;
    }
} runs[N * 2 + 5];
int tot;
int main()
{
    scanf("%s",s + 1),n = strlen(s + 1),pw[0] = 1;
    for(register int i = 1;i <= n;++i)
        pw[i] = (long long)pw[i - 1] * P % mod,
        hs[i] = ((long long)hs[i - 1] * P + s[i] - 'a' + 1) % mod;
    for(register int op = 0;op <= 1;++op)
    {
        lyndon(op);
        for(register int i = 1,lcp,lcs;i < n;++i)
            lcp = LCP(i,ly[i] + 1),lcs = LCS(i - 1,ly[i]),
            lcp + lcs >= ly[i] - i + 1 && (runs[++tot] = (Run){i - lcs,ly[i] + lcp,ly[i] - i + 1},1);
    }
    sort(runs + 1,runs + tot + 1),tot = unique(runs + 1,runs + tot + 1) - runs - 1;
    printf("%d\n",tot);
    for(register int i = 1;i <= tot;++i)
        printf("%d %d %d\n",runs[i].l,runs[i].r,runs[i].p);
}

Primitive Square

Three Square Lemma

对 u,v,w 满足 uu 是 vv 的前缀，vv 是 ww 的前缀，且 uu 是本原平方串，有 |u|+|v|≤w。

推论 1

本原平方串的个数是 O(nlogn) 级别的。

推论 2

本质不同的本原平方串的个数是 O(n) 级别的。

推论 3

一个字符串所有 run r=(l,r,p) 的 r−l+2−2p 之和是 O(nlogn) 级别的。