字符串备忘录

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

Lyndon 分解 - Duval 算法

Lyndon 分解的定义略。

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

  • \(s[1\dots i-1] = s_1 s_2 \dots s_g\) 是已经确定的分解。

  • \(s[i\dots k-1] = t^h + v\) 是待定的分解,其中 \(t\) 是一个 Lyndon Word,\(h > 1\)\(v\)\(t\) 的真前缀,且 \(s_g \ge s[i\dots k-1]\)

同时维护 \(j = k - |t|\),考虑 \(s[k]\),分类讨论

  • \(s[j]=s[k]\),则周期继续维持,\(j \gets j+1,k \gets k+1\)

  • \(s[j]<s[k]\)\(v + s[k]\) 为 Lyndon Word,将 \(t^h + v + s[k]\) 合并为一个新的 Lyndon Word \(t\),即令 \(j\gets i\)

  • \(s[j]>s[k]\),确定 \(t^h\) 的分解,算法从 \(v\) 的开头继续。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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

\[ \rho(n) < n,\sigma(n) < 3n-3 \]

求 Runs

\(<_0,<_1\)\(\Sigma\) 上两种相反的全序关系,类似地定义到 \(\Sigma*\) 上的字典序关系。
对于 \(\ell \in \{0,1\}\),令 \(\overline \ell = 1-\ell\)

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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| \le w\)

推论 1

本原平方串的个数是 \(O(n \log n)\) 级别的。

推论 2

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

推论 3

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