字符串备忘录

发表于 | 分类于 |

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

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)\) 级别的。

Gitalking ...