字符串

卡布叻_米菲 Lv2

content: 字符串有关的标准库,KMP算法(寻找子串的高效算法,在 文本串s 中快速寻找 模式串p 的一种算法),Z算法,字典树,Manacher算法,后缀数组

[TOC]

标准库

C 标准库

C 标准库操作字符数组。

char[]/const char*

参见:fprintf fscanf 空终止字节字符串

  • printf("%s", s):用 %s 来输出一个字符串(字符数组)。
  • scanf("%s", &s):用 %s 来读入一个字符串(字符数组)。
  • sscanf(const char *__source, const char *__format, ...):从字符串 __source 里读取变量,比如 sscanf(str,"%d",&a)
  • sprintf(char *__stream, const char *__format, ...):将 __format 字符串里的内容输出到 __stream 中,比如 sprintf(str,"%d",i)
  • strlen(const char *str):返回从 str[0] 开始直到 '\0' 的字符数。注意,未开启 O2 优化时,该操作写在循环条件中复杂度是 (N) 的。
  • strcmp(const char *str1, const char *str2):按照字典序比较 str1 str2str1 字典序小返回负值,两者一样返回 0str1 字典序更大则返回正值。请注意,不要简单的认为返回值只有 01-1 三种,在不同平台下的返回值都遵循正负,但并非都是 01-1
  • strcpy(char *str, const char *src): 把 src 中的字符复制到 str 中,str src 均为字符数组头指针,返回值为 str 包含空终止符号 '\0'
  • strncpy(char *str, const char *src, int cnt):复制至多 cnt 个字符到 str 中,若 src 终止而数量未达 cnt 则写入空字符到 str 直至写入总共 cnt 个字符。
  • strcat(char *str1, const char *str2): 将 str2 接到 str1 的结尾,用 *str2 替换 str1 末尾的 '\0' 返回 str1
  • strstr(char *str1, const char *str2):若 str2str1 的子串,则返回 str2str1 的首次出现的地址;如果 str2 不是 str1 的子串,则返回 NULL
  • strchr(const char *str, int c):找到在字符串 str 中第一次出现字符 c 的位置,并返回这个位置的地址。如果未找到该字符则返回 NULL
  • strrchr(const char *str, char c):找到在字符串 str 中最后一次出现字符 c 的位置,并返回这个位置的地址。如果未找到该字符则返回 NULL

C++ 标准库

C++ 标准库操作字符串对象,同时也提供对字符数组的兼容。

std::string

参见:std::basic_string

  • 重载了赋值运算符 +,当 + 两边是 string/char/char[]/const char* 类型时,可以将这两个变量连接,返回连接后的字符串(string)。
  • 赋值运算符 = 右侧可以是 const string/string/const char*/char*
  • 访问运算符 [cur] 返回 cur 位置的引用。
  • 访问函数 data()/c_str() 返回一个 const char* 指针,内容与该 string 相同。
  • 容量函数 size() 返回字符串字符个数。
  • find(ch, start = 0) 查找并返回从 start 开始的字符 ch 的位置;rfind(ch) 从末尾开始,查找并返回第一个找到的字符 ch 的位置(皆从 0 开始)(如果查找不到,返回 -1)。
  • substr(start, len) 可以从字符串的 start(从 0 开始)截取一个长度为 len 的字符串(缺省 len 时代码截取到字符串末尾)。
  • append(s)s 添加到字符串末尾。
  • append(s, pos, n) 将字符串 s 中,从 pos 开始的 n 个字符连接到当前字符串结尾。
  • replace(pos, n, s) 删除从 pos 开始的 n 个字符,然后在 pos 处插入串 s
  • erase(pos, n) 删除从 pos 开始的 n 个字符。
  • insert(pos, s)pos 位置插入字符串 s
  • std::string 重载了比较逻辑运算符,复杂度是 O(N) 的。

KMP算法

设两个字符串的长度分别是 n 和 m,则暴力匹配的最坏时间复杂度是 O(nm)。

暴力解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int i = 0, j = 0;
while(i < s.length())
{
if(s[i] == p[j])
i++, j++;
else
i = i-j+1, j = 0;
if(j == p.length()) //匹配成功
{
cout << i-j << endl;
i = i-j+1;
j = 0;
}
}

每次匹配失败时候,i 都要回溯,同时 j 置零。

分析算法

KMP算法引入 PMT(Partial Match Table,部分匹配表),能让 j 被赋予一个合适的值。

假设 文本串为 abababcabaa,模式串为 ababcabaa

j 应该被赋予多少值,是只与模式串自身有关的。每个模式串,都对应着一张PMT,比如:

模式串 ababcabaa对应的PMT如下:

img

pmt[i] 就是,从 p[0] 往后数,同时从 p[i] 往前数相同的位数,在保证前后缀相同的情况下,最多能数多少位。(但要小于p的长度)

img

专业点说,它是 真前缀 与 真后缀 的集合的中,最长元素的长度。

实例说明:

在暴力匹配中的情形:

img img

遇到不同的字母,暴力选择将 j 前移,但是观察可知,前面 abab 匹配成功,它的前缀和后缀有重叠部分 'ab',我们可以将这个与前缀相同的后缀利用起来得到,在第二张图中,pmt[4] = 2,当遇到 这种不匹配的情况时,j 的变化为:j = ptm[4] = ptm[i-1]

再举个例子:

img

发生失配时,我们可以直接令 j = pmt[i-1](也就是符合条件的最长前缀紧接着的下一位)。

代码过程为:

1
2
3
4
5
6
7
8
9
10
for(int i = 0, j = 0; i<s.length(); i++)
{
while(j && s[i]!=p[j]) j = pmt[j-1]; //遇到不匹配的,前移指针 j
if(s[i] == p[j]) j++; //匹配成功,j 右移
if(j == p.length())
{
//对 s[i-j+1] 进行操作
j = pmt[j-1];
}
}

很多文章中会使用next数组,即把PMT整体向右移一位(特别地,令next[0]=-1),表示在每一位失配时应跳转到的索引。也就是说,失配时,按照i -> next[i] -> next[next[i]] -> ...的顺序跳转。其实原理和实现都是差不多的。

求PMT数组

如果暴力求解时间复杂度 ,并不理想。精妙的做法是:错开一位后,让 p 自己匹配自己(这相当于 用前缀去匹配后缀)。我们知道 pmt[0] = 0,而之后的每一位则可以通过在匹配过程中记录 j 值得到。

还是以下面的模式串为例:

img img

匹配失败,则pmt[1] = -1+1 = 0,i指针右移,接下来匹配成功,pmt[2] = 1,然后两个指针都右移

img

继续匹配成功,j指针右移,pmt[3] = 2,下一位失配,因为前面的 pmt 已经算出来了,我们可以像文本串匹配时那样使用它。pmt[2-1]pmt[1]等于0,所以退回到开头。

img

j指针已经到了开头,仍未匹配成功,所以不再移动,pmt[4]=j=0。接下来也按这种方法操作

img

最后一位出现失配,这次我们先令j=pmt[j-1]=1,再次匹配,匹配成功,j指针右移一位,pmt[i]=j=1。自此,我们通过一趟自我匹配,求出了PMT。

代码:

1
2
3
4
5
6
7
//pmt[0] = 0
for(int i = 0, j = 0; i<plen; i++)
{
while(j && p[i]!=p[j]) j = pmt[j-1];
if(p[i] == p[j]) j++;
pmt[i] = j;
}

例题

洛谷P3375 【模板】KMP字符串匹配

题目描述

给出两个字符串 s1 和 s2,若 s2 的区间[l, r]子串与 s2 完全相同,则称 s2 在 s1 中出现了,其出现位置为 l。 现在请你求出 s2 在 s1 中所有出现的位置。

定义一个字符串s 的 border 为s 的一个非s本身的子串 t,满足 t 既是 s 的前缀,又是 s 的后缀。 对于s2,你还需要求出对于其每个前缀 s' 的最长 border t' 的长度。

输入格式

第一行为一个字符串,即为 s1。 第二行为一个字符串,即为 s2。

输出格式

首先输出若干行,每行一个整数,按从小到大的顺序输出 s2 在 s1 中出现的位置。 最后一行输出 ∣s2∣ 个整数,第 i 个整数表示 s2 的长度为2 的前缀的最长 border 长度。

代码

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
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int pmt[MAXN];
void get_pmt(const string& s)
{
for(int i = 1, j = 0; i<s.length(); i++)
{
while(j && s[i]!=s[j]) j = pmt[j-1];
if(s[i] == s[j]) j++;
pmt[i] = j;
}
}
void kmp(const string& s, const string& p)
{
for(int i = 0,j = 0; i<s.length(); i++)
{
while(j && s[i]!=p[j]) j = pmt[j-1];
if(s[i] == p[j]) j++;
if(j == p.length())
{
cout << i-j+2; << endl;
j = pmt[j-1];
}
}
}
int main()
{
ios::sync_with_stdio(false);
string s, p;
cin >> s >> p;
get_pmt(p);
kmp(s, p);
for(int i = 0; i<p.length(); i++)
cout << pmt[i] << ' ';
return 0;
}

上面的算法只能称为 MP算法,真正的KMP算法,使用 nextval数组

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
int nextval[MAXN];
string s, p;
int main()
{
ios::sync_with_stdio(false);
cin >> s >> p;
for (int i = 1, j = 0; i < p.length(); ++i)
{
while (j >= 0 && p[i] != p[j])
j = j ? nextval[j - 1] : -1;
nextval[i] = j >= 0 && p[i + 1] == p[j + 1] ? nextval[j++] : ++j;
}
for (int i = 0, j = 0; i < s.length(); ++i)
{
while (s[i] != p[j] && j >= 0)
j = j ? nextval[j - 1] : -1;
j++;
if (j == p.length())
{
cout << i - j + 2 << endl;
j = nextval[j - 1];
}
}
cout << endl;
return 0;
}

Z 算法

Z算法(Z-Algorithm)是一种字符串算法,在国内也常常被叫做拓展KMP算法

KMP算法 的核心就是那张 部分匹配表,其实它被称为 前缀函数,记作 。对一个字符串而言,我们定义 既是它前缀又是它后缀的字符串是它的 border,那 就表示 的最大border 的长度。或者说, 是满足 的最大的 (特别地,令

而 Z算法的核心 是 Z函数,它的定义与 非常相似。 定义为 最长公共前缀(LCP)。或者说, 是满足 的最大的 x(特别地,令

例如,设有字符串aabcaabcaaaab,那么它的Z函数值如下表所示:

img

算法过程

,那么我们定义区间 为一个 Z-Box,显然,Z-Box 对应的子串一定也是整个字符串的一个前缀。例如,上表中 [4, 9] 就是一个 Z-Box,它对应的子串是 aabcaa,也是整个字符串的一个前缀。

我们从左往右枚举下标 ,同时维护 ,用 表示 最大的 Z-Box。那么就可能出现三种情况:

  • 如果 ,说明我们已经完全越过了上一个 Z-Box,任何一个新的Z-Box 的 r 都会更大,这时 我们直接逐个比较,暴力计算 的值。计算完成后,如果 ,则更新

    1
    2
    3
    4
    5
    6
    if(i > r)
    {
    while(i+z[i] < n && s[z[i]] == s[i+z[i]])
    z[i]++;
    l = i, r = i+z[i]-1;
    }

    img

  • 如果 ,此时已经知道了 是相等的,因此 也是相等的。所以我们考虑 ,说明从 开始匹配 和 从 开始匹配是 一样的——匹配一定会在离开 Z-Box 前停止。即,

    1
    2
    else if(z[i-l] < r-i+1)
    z[i] = z[i-l];

    img

  • 如果 ,说明整个 Z-Box 的剩余部分都可以匹配,但后面的情况我们不清楚,所以不能说 。但我们知道 至少有 ,接下来我们暴力计算 Z-Box 还能向后延长多少即可

    1
    2
    3
    4
    5
    6
    7
    else
    {
    z[i] = r-i+1;
    while(i+z[i] < n && s[z[i]] == s[i+z[i]])
    z[i]++;
    l = i, r = i+z[i]-1;
    }

    img

综合分析可以发现 第一种和第三种情况可以合并,最终得到:

1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 1, l = 0, r = 0; i<n; i++)
{
if(z[i-l] < r-i+1)
z[i] = z[i-l]
else
{
z[i] = max(r-i+1, 0);
while(i+z[i]<n && s[z[i]] == s[i+z[i]])
z[i]++;
l = i, r = i+z[i]-1;
}
}

时间复杂度:O(N)

简单应用

给出字符串 a, b,求 a 的每个后缀与 b 的LCP

设 @ 为字符集外字符,求 b+@+a 的 Z 函数,则 a 的后缀 a[i..] 与 b 的 LCP 为 Z(|b|+1+i)。

给出文本串 s 和 模式串 p,求 p 在 s 中的所有出现位置

这是 KMP 和字符串哈希的经典题目,但也可以用 Z 算法。设 @ 为 字符集外字符,求 p+@+s 的Z 函数,则每个Z(i) = |p| 都对应 p 在 s 中的一次出现。

求 s 的所有 border

虽然是 纯KMP 题,但也可以用 Z算法。求 s 的 Z 函数。对于每一个 i,如果 i+Z(i) = |s|,说明这个 Z-Box 对应一个 border。(注:与 KMP 不同,这里只是求所有 border,不是求所有的向前 border)

求 s 的每个前缀出现的次数

求 s 的 Z 函数。对于每一个 i,如果 Z(i) 不等于 0,说明长度为 Z(i), Z(i)-1,..., 1 的前缀在次数各出现了一次,所以求一个后缀和即可。在这个问题一般令 Z(0) = |s|。

1
2
3
4
for(int i = n+1; i<2*n+1; i++)
S[z[i]]++;
for(int i = n; i>=1; i--)
s[i] += s[i+1];

Manacher算法

介绍

Manacher算法,俗称 马拉车,是一种与 回文子串 有关的算法。

回文串根据长度的奇偶性可以分为 奇回文串 和 偶回文串 两种。奇回文串 通常比偶回文串好处理,因为 它有一个中心,而且可以从中心往两边同时拓展。

对字符串进行预处理可以用处理 回文串的方法处理 偶回文串。方法是:在每队相邻字符和字符串的两端加入一个 字符集外字符(这里设为 @),例如 abbab 变成 @a@b@b@a@b@。这样处理后,原来的 bab 变成了 @b@a@b@,原来的 abba 变成了 @a@b@b@a@。可以发现,原来的 奇回文子串 会变成以普通字符为中心的 奇回文子串;原来的 偶回文子串 会变成以 @为中心的 奇回文子串。

对于一个字符串 s,设 d[i] 表示以 s[i] 为中心的 奇回文子串 的数量。很明显,d[i] 个回文子串 的长度分别为 1, 3, ..., 2d[i]-1。如果 s 是由 t 预处理得到的,那么这些回文子串对应 t 中对应位置的 个回文子串,且最长的一个长度为 d[i]-1。

Manacher算法的作用,就是 O(n) 地求出 这个 d 数组。

分析

Manacher算法其实和 Z算法 的流程非常类似。从左往右枚举 ,并维护 ,使得 是满足 最靠右的 奇回文串。当我们枚举到一个新的 时,我们进行分类讨论:

  • 如果 ,则直接暴击计算 d[i],同时更新 l 和 r。

    img

    1
    2
    3
    4
    5
    6
    if(i > r)
    {
    while(i-d[i]>=0 && i+d[i]<n && s[i-d[i]] == s[i+d[i]])
    d[i]++;
    l = i-d[i]+1, r = i+d[i]-1;
    }
  • 如果 ,找到 关于 中心的对称点 ,这时如果以 为中心的最长奇回文串的左边界大于 ,则直接令 。这是因为,在 的范围内,关于中心点对称的子串一定是相等的。

    img

    1
    2
    3
    4
    5
    //i<= r int j = l+r-i;
    else if(j - d[j] >= l) //即 j-d[j]+1 > l
    {
    d[i] = d[j];
    }
  • 如果以 为中心的最长奇回文串的左边界小于等于 ,那么我们知道 至少有 (或),但会不会更长还不清楚,所以要进行左右拓展,同时更新

    img

    1
    2
    3
    4
    5
    6
    7
    else
    {
    d[i] = j-l+1;
    while(i-d[i] >= 0 && i+d[i] < n && s[i-d[i]] == s[i+d[i]])
    d[i]++;
    l = i-d[i]+1, r = i+d[i]-1;
    }

综合分析,得到以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = 0, l = 0, r = -1; i<n; i++)
{ // j = l+(r-i) 是 i 在[l...r]中的关于中心对称点
int j = l+r-i; dj = j>0? d[j] : 0;
d[i] = max(min(dj, j-l+1), 0);
// i<=r, j-dj>=l,则 d[i] = d[j]
// i>r, j < l,则 j - dj必然小于 l,两种情况可以合成 j-dj < 1 的情况
if(j - dj < l) // i>r 或 i<=r && j - d[j] < l 进入循环
{
while(i-d[i] >= 0 && i+d[i]<n && s[i-d[i]] == s[i+d[i]])
d[i]++;
l = i-d[i]+1, r = i+d[i]-1;
}
}

时间复杂度为:

字典树

字典树(Trie) 是一种比较简单的数据结构,也叫 前缀树,用来存储和查询字符串。例如:waterwishwintietired这几个单词可以用以下方式存储:

img

其中每个字符占据一个节点,拥有相同前缀的字符串可以公用部分节点。起点是特殊点(设为1号点),不存储字符。建树的代码如下:

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
struct trie 
{
int nex[100000][26], cnt;
bool exist[100000]; // 该结点结尾的字符串是否存在

void insert(char *s, int l)
{ // 插入字符串
int p = 0;
for (int i = 0; i < l; i++)
{
int c = s[i] - 'a';
if (!nex[p][c]) nex[p][c] = ++cnt; // 如果没有,就添加结点
p = nex[p][c];
}
exist[p] = 1;
}

bool find(char *s, int l)
{ // 查找字符串
int p = 0;
for (int i = 0; i < l; i++)
{
int c = s[i] - 'a';
if (!nex[p][c]) return 0;
p = nex[p][c];
}
return exist[p];
}
};

应用

检索字符串

字典树最基础的应用——查找一个字符串是否在「字典」中出现过。

于是他错误的点名开始了

给你 n 个名字串,然后进行 m 次点名,每次你需要回答「名字不存在」、「第一次点到这个名字」、「已经点过这个名字」之一。

,所有字符串长度不超过 50。

分析:对所有名字建 trie,再在 trie 中查询字符串是否存在、是否已经点过名,第一次点名时标记为点过名。

题解:

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
#include <cstdio>

const int N = 500010;

char s[60];
int n, m, ch[N][26], tag[N], tot = 1;

int main()
{
scanf("%d", &n);

for (int i = 1; i <= n; ++i)
{
scanf("%s", s + 1);
int u = 1; // 指向根节点
for (int j = 1; s[j]; ++j)
{
int c = s[j] - 'a';// 计算字符对应的下标
if (!ch[u][c])
ch[u][c] = ++tot;
// 如果这个节点的子节点中没有这个字符,添加上并将该字符的节点号记录为++tot
u = ch[u][c]; // 往更深一层搜索
}
tag[u] = 1; // 最后一个字符为节点 u 的名字未被访问到记录为 1
}

scanf("%d", &m);

while (m--)
{
scanf("%s", s + 1);
int u = 1;// 指向根节点
for (int j = 1; s[j]; ++j)
{
int c = s[j] - 'a'; // 计算字符对应的下标
u = ch[u][c];// 指向下一个节点
if (!u) break; // 不存在对应字符的出边说明名字不存在
}
if (tag[u] == 1) // 前缀存在
{
tag[u] = 2; // 最后一个字符为节点 u 的名字已经被访问
puts("OK");
}
else if (tag[u] == 2) // 已经被访问,重复访问
puts("REPEAT");
else
puts("WRONG");
}

return 0;
}

维护异或极值

将数的二进制表示看作一个字符串,就可以建出字符集为 {0, 1} 的 trie 树

BZOJ1954 最长异或路径

给你一棵带边权的树,求 (u, v) 使得 u 到 v 的路径上的边权异或和最大,输出这个最大值。

点数不超过 ,边权在 内。

分析:

指定一个根 root,用 T(u, v) 表示 u 和 v 之间路径的边权异或和,那么 ,因为 LCA 以上的部分异或两次抵消了。

那么,如果将所有 T(root, u) 插入到一棵 trie 中,就可以对每个 T(root, u) 快速求出和它异或和最大的 T(root, v):从 trie 的根开始,如果能向和 T(root, u) 的当前位不同的子树走,就向那边走,否则没有选择。

贪心的正确性:如果这么走,这一位为 1;如果不这么走,这一位就会为 0。而高位是需要优先尽量大的。

维护异或和

01-trie 是指 字符集为 {0, 1} 的 trie。01-trie 可以用来维护一些数字的异或和,支持修改(删除+重新插入),和全局加一(即:让其所维护所有数值递增 1,其本质上是一种修改操作)

如果要维护异或和,需要按值从低位到高位建立 trie。

一个约定:文中说当前节点 往上 指当前节点到根这条路径,当前节点 往下 指当前节点的子树。

插入 & 删除

如果要维护 异或和,我们 只需要 知道某一位上 0 和 1 个数的 奇偶性 即可,也就是对于数字 1 来说,当且仅当这一位上 数字 1 的个数为奇数时,这一位上的数字 才是 1。

注意:如果只是维护 异或和,我们只需要知道某一位上 1 的数量即可,而不需要知道 trie 到底维护了哪些数字。

对于每一个节点,我们需要记录以下三个量:

  • ch[o][0/1] 指节点 o 的两个儿子,
  • ch[o][0] 指下一位是 0,同理 ch[o][1] 指下一位是 1
  • w[o] 指节点 o 到其父亲节点这条边上数值的数量(权值)。每插入一个数字 xx 二进制拆分后在 trie 上 路径的权值都会 +1
  • xorv[o] 指以 o 为根的子树维护的异或和。

具体维护节点的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void maintain(int o)
{
w[o] = worx[o] = 0;
if(ch[o][0])
{
w[o] += w[ch[o][0]];
xorv[o]^=xorv[ch[o][0]] << 1;
}
if(ch[o][1])
{
w[o]+=w[ch[o][1]];
worv[o] ^= (xorv[ch[o][1]] << 1) | (w[ch[o][1]] & 1);
}
// w[o] = w[o] & 1;
// 只需知道奇偶性即可,不需要具体的值。当然这句话删掉也可以,因为上文就只利用了他的奇偶性。
}

插入和删除的代码非常相似。在代码中:MAXH 指 trie 的深度,也就是让每个叶子节点到根节点的距离为 MAXH。对于一些比较小的值,可能有时候不需要建立那么深(例如:如果插入数字 4,分解为二进制后为 100,从根除插入 001 这三位即可),但是我们强制插入 MAXH 位,这样做是为了便于 全局 +1 时处理进位。例如:如果原数字是 311),递增之后变成4100),如果插入 3 时只插入 2 位,那这里的进位就没了。

插入和删除,只需要修改叶子节点的 w[] 即可,在回溯的过程中一路维护即可。

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
namespace trie{
const int MAXH = 21;
int ch[_*(MAXH+1)][2], w[_* (MAXH+1)], xorv[_*(MAXH+1)];
int tot = 0;

int mknode() //创建节点
{
++tot;
ch[tot][1] = ch[tot][0] = w[tot] = xorv[tot] = 0;
return tot;
}

void maintain() //维护节点的权值和yi
{
w[o] = xorv[o] = 0;
if(ch[o][0])
{
w[o] += w[ch[o][0]];
xorv[o] ^= xorv[ch[o][0]] << 1;
}
if(ch[o][1])
{
w[o] += w[ch[o][1]];
xorv[o] ^= (xorv[ch[o][1]] << 1) | (w[ch[o][1]] & 1);
}
w[o] = w[o] & 1;
}

void insert(int &o, int x, int dp) //插入一个数
{ //dp 表示当前处理到二进制数的第几位
if(!o) o = mknode(); //如果当前节点不存在,则创建一个新节点
if(dp>MAXH) return (void)(w[o]++); //如果dp大于 MAXH,则节点权值+1
insert(ch[o][x&1], x>>1, dp+1); //否则,递归插入 x 的下一位
maintain(o); //维护节点的权值和异或和
}

void erase(int o, int x, int dp) //删除一个数x,dp表示处理二进制数的第几位
{
if(dp > 20) return (void)(w[o]--); //dp大于 MAXH,则将该节点权值-1
erase(ch[o][x&1], x>> 1, dp+1); //递归处理删除 x 的下一位
maintain(o); //维护节点的下一位
}
}

全局加一

让这棵 trie 中所有的数值 +1

设 trie 中维护的数值有 , 全局 +1 后 其中维护的值应该变成

1
2
3
4
5
6
void addall(int o)
{
swap(ch[o][0], ch[o][1]);
if(ch[o][0]) addall(ch[o][0]);
maintain(o);
}

对应 trie 的操作,其实就是交换其左右儿子,顺着 交换后0 边往下递归操作即可。

回顾一下 w[o] 的定义:w[o] 指节点 o 到其父亲节点这条边上数值的数量(权值)。

有没有感觉这个定义有点怪呢?如果在父亲结点存储到两个儿子的这条边的边权也许会更接近于习惯。但是在这里,在交换左右儿子的时候,在儿子结点存储到父亲这条边的距离,显然更加方便。

01-trie 合并

将上述两个 01-trie 进行合并,同时维护的信息。

实现分三种情况:

  • 如果 a 没有这个位置上的结点,新合并的结点就是 b

  • 如果 b 没有这个位置上的结点,新合并的结点就是 a

  • 如果 a,b 都存在,那就把 b 的信息合并到 a 上,新合并的结点就是 a,然后递归操作处理 a 的左右儿子。

    提示:如果需要的合并是将 a,b 合并到一棵新树上,这里可以新建结点,然后合并到这个新结点上,这里的代码实现仅仅是将 b 的信息合并到 a 上。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int merge(int a, int b) {
if (!a) return b; // 如果 a 没有这个位置上的结点,返回 b
if (!b) return a; // 如果 b 没有这个位置上的结点,返回 a
/*
如果 `a`, `b` 都存在,
那就把 `b` 的信息合并到 `a` 上。
*/
w[a] = w[a] + w[b];
xorv[a] ^= xorv[b];
/* 不要使用 maintain(),
maintain() 是合并a的两个儿子的信息
而这里需要 a b 两个节点进行信息合并
*/
ch[a][0] = merge(ch[a][0], ch[b][0]);
ch[a][1] = merge(ch[a][1], ch[b][1]);
return a;
}

其实 trie 都可以合并,换句话说,trie 合并不仅仅限于 01-trie。

后缀数组

后缀数组(Suffix Array, SA)是解决很多与字符相关的问题的有力工具。它实际上就是把字符串所有 后缀字典序 排序后得到的数组。

显然,直接使用 std::sort 函数 时间复杂度 。用倍增的思想,可以把复杂度优化为

首先,把字符串的长度扩充一倍,保证往后填充的字符比所有已有的字符都小(记为 0)。注意,这样填充后并不会影响原先 两个后缀的大小相对关系。

img

表示 第 位开始、长度为 的子串在 所有长度为 的子串中的排名(全 0 串的排名记为 0), 表示长度为 的子串中字典序第 小的一个的开始位置。

我们可以轻松地求出

img

如果我们已经知道了 ,那么我们可以求出 ——只需要以 为第一关键词、 为第二关键词对 进行一次排序就好。而,如果我们得到 ,自然可以得到

原理:对于两个等长的字符串 s 和 t,如果 s 的字典序小于 t,那么要么 s 的前半段的字典序小于 t 的后半段的字段序。

img

所以我们可以从 出发, 进一步得到 ...... 。当 时, 也可以表示每个后缀的排名, 也可以表示每个 后缀 排序后的结果,也就是我们要的后缀数组。

在实际实现过程中,我们不需要求出 。因为除了最后一步外,我们只需要知道 的相对大小关系,所以 可以用字符本身代替。而除了最后一步外, 的唯一作用就是求 ,但 没有被用来求 ,只是一个待排序数组,所以把待排序的下标按任意顺序放进去即可。不过 当n=1时,这样做会得到错误的 rk,可以特判一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char s[MAXN];
int rk[MAXN << 1], sa[MAXN], tmp[MAXN << 1];
//排名数组 rk-第i位的w长度数组在所有长度w的子串的排名
//后缀数组 sa-长度w的子串第i小的开始位置
void init_sa(int n) //初始化 后缀数组
{
if(n == 1) return void(rk[1] = sa[1] = 1); //特判
for(int i = 1; i<=n; i++)
sa[i] = i, rk[i] = s[i];
for(int w = 1; w<n; w<<=1) //w <<= 1 相当于 *2,但是运算速度更快
{
auto rp = [&](int x) { return make_pair(rk[x], rk[x+w]); }
sort(sa+1, sa+n+1, [&](int x, int y){ return rp(x) < rp(y);});
//排序的依据是每个后缀的前w个字符和后w个字符组成的二元组,即(rp(x), rp(x+w)),其中rp(x)表示x后缀的排名,rp(x+w)表示x后缀后w个字符的排名。这里使用了匿名表达式,将(rp(x), rp(x+w))作为排序的依据。
for(int i = 1, p = 0; i<=n; i++)
tmp[sa[i]] = rp(sa[i-1]) == rp(sa[i])? p: ++p;
//相同的子串具有相同的排名
copy(tmp+1, tmp+n+1, rk+1);
//最后将tmp数组的值复制到rk数组中,为下一轮排序做准备。
}
}

降低复杂度:计数排序 代替 std::sort,时间复杂度

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
char s[MAXN];
int rk[MAXN << 1], sa[MAXN], tmp[MAXN << 1], cnt[MAXN];
//后缀数组 sa,排名数组 rk,临时数组 tmp 和计数数组 cnt
void init_sa(int n)
{
if(n == 1) return void(rk[1] = sa[1] = 1);

for(int i = 1; i<=n; i++)
sa[i] = i, rk[i] = s[i];
//将后缀数组初始化为 1,2,⋯,n,将排名数组初始化为输入字符串的字符对应的 ASCII 码。
for(int w = 1, m = max(128, n); w<n; w<<=1)
{
fill(cnt+1, cnt+m+1, 0);
for(int i = 1; i<=n; i++) cnt[rk[sa[i]+w]]++;
for(int i = 1; i<=m; i++) cnt[i] += cnt[i-1];
for(int i = n; i>=1; i--)
temp[cnt[rk[sa[i]+w]]--] = sa[i];

fill(cnt+1, cnt+m+1, 0);
for(int i = 1; i<=n; i++) cnt[rk[tmp[i]]]++;
for(int i = 1; i<=m; i++) cnt[i] += cnt[i-1];
for(int i = n; i>=1; i--)
sa[cnt[rk[tmp[i]]]--] = tmp[i];

auto rp = [&](int x) { return make_pair(rk[x], rk[x+w]); }
for(int i = 1, p = 0; i<=n; i++)
tmp[sa[i]] = rp(sa[i-1]) == rp[sa[i]]?p:++p;
copy(tmp+1, tmp+n+1, rk+1);
}
}

常数优化,在 n 较大的情况下能更快速

我们每次需要遍历 max(n, 128) 个数,实际上是很浪费的。注意到,我们每次都计算出了一个 ,它其实就是 cnt 的值域。实际上,除了第一次循环后值域可能减小,cnt 的值域都是逐渐增长到 n 的。而且当它增长到 n 时,说明每个子串的 rk 互不相同,数组已经不会再有变化了,这时可以提前退出。

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
char s[MAXN];
int rk[MAXN << 1], sa[MAXN << 1], tmp[MAXN << 1], cnt[MAXN], rkt[MAXN];
void init_sa(int n) { // 1-index
if (n == 1) return void(rk[1] = sa[1] = 1);

int m = 128;
for (int i = 1; i <= n; ++i)
++cnt[rk[i] = s[i]];
for (int i = 1; i <= m; ++i)
cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i)
sa[cnt[rk[i]]--] = i;

for (int w = 1;; w <<= 1) {
for (int i = n; i > n - w; --i)
tmp[n - i + 1] = i;
for (int i = 1, p = w; i <= n; ++i)
if (sa[i] > w) tmp[++p] = sa[i] - w;
fill(cnt + 1, cnt + m + 1, 0);
for (int i = 1; i <= n; ++i)
cnt[rkt[i] = rk[tmp[i]]]++;
for (int i = 1; i <= m; ++i)
cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i)
sa[cnt[rkt[i]]--] = tmp[i];
m = 0;
auto rp = [&](int x) { return make_pair(rk[x], rk[x + w]); };
for (int i = 1; i <= n; ++i)
tmp[sa[i]] = rp(sa[i - 1]) == rp(sa[i]) ? m : ++m;
copy(tmp + 1, tmp + n + 1, rk + 1);
if (n == m) break;
}
}

洛谷上与后缀数组有关的题目:

  1. P3805 【模板】后缀数组
  2. P3806 【模板】后缀数组 2
  3. P3807 【模板】后缀数组 3
  4. P3808 【模板】后缀数组 4
  5. P3809 【模板】后缀数组 5
  6. P3375 【模板】KMP字符串匹配
  7. P3376 【模板】AC自动机(字符串多模式匹配)
  8. P3803 【模板】广义后缀自动机
  9. P3804 【模板】广义后缀数组
  10. P3802 【模板】SAM模板

后缀的最长公共前缀

我们令 ,其中 lcp 表示最长公共前缀。利用这个 height 数组,可以解决很多问题。

首先,求 height 数组,一个结论很重要:

,则 恒成立

分析结论:比如某个后缀为 cxz,它的上一个后缀为 cxy(字典序),则 LCP 就是 cx(长度记为 h[i-1])。现在考察它下一个后缀(编号意义下)xz,我们已经知道字符串存在一个后缀 xy,字典序比 xz 小,而且它与 xz 的 LCP 为 x(长度为 h[i-1]-1),则有

利用这个结论,O(n) 求出 height 数组

1
2
3
4
5
6
7
8
9
10
void init_ht(int n)
{
for(int i = 1,k = 0; i<=n; i++)
{
if(k>0) k--;
while(s[i+k] == s[sa[rk[i]-1]+k])
k++;
ht[rk[i]] = k;
}
}

解决的问题:

  • 按字典序遍历所有本质不同的子串。只需要遍历 的前缀,但是跳过前 height[i] 个,因为这 height[i] 个前缀是与 sa[i-1] 共有的,之前一定已经被遍历过。按此道理,也可以知道字符串本质不同的字符串数量为
  • 可以求两个子串的 LCP。显然设两个子串为 。则它们的最长公共前缀为 min(|s1|, |s2|, lcp(sa[l1], sa[l2]))。所以我们只需要求两个后缀的 LCP,而很容易发现这正是 min(height[k]) (l1 <= k <= l2)

串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words words 中所有字符串 长度相同

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef""abefcd""cdabef""cdefab""efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。

返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1:

1
2
3
4
5
6
输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2:

1
2
3
4
5
输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3:

1
2
3
4
5
6
输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]
解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示:

  • 1 <= s.length <= 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i]s 由小写英文字母组成

分析

暴力枚举+哈希映射

首先,最直接的思路,判断每个子串是否符合,符合就把下标保存下来,最后返回即可。怎么判断子串是否符合?这也是这个题的难点了,由于子串包含的单词顺序并不需要固定,如果是两个单词 A,B,我们只需要判断子串是否是 AB 或者 BA 即可。如果是三个单词 A,B,C 也还好,只需要判断子串是否是 ABC,或者 ACB,BAC,BCA,CAB,CBA 就可以了,但如果更多单词呢?那就崩溃了。

用两个 HashMap 来解决。首先,我们把所有的单词存到 HashMap 里,key 直接存单词,value 存单词出现的个数(因为给出的单词可能会有重复的,所以可能是 1 或 2 或者其他)。然后扫描子串的单词,如果当前扫描的单词在之前的 HashMap 中,就把该单词存到新的 HashMap 中,并判断新的 HashMap 中该单词的 value 是不是大于之前的 HashMap 该单词的 value ,如果大了,就代表该子串不是我们要找的,接着判断下一个子串就可以了。如果不大于,那么我们接着判断下一个单词的情况。子串扫描结束,如果子串的全部单词都符合,那么该子串就是我们找的其中一个。

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
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> ans;
int len = words[0].length();
int sumlen = len*words.size();
if(s.length() < sumlen) return ans;

unordered_map<string, int> ms;
for(int i = 0; i<words.size(); i++)
ms[words[i]]++;

for(int i = 0; i<=s.length()-sumlen; i++)
{
map<string, int> subms;
int flag = true;
for(int j = i; j<i+sumlen; j+=len)
{
string subs = s.substr(j, len);
if(ms.count(subs) == 0)
{
flag = false;
break;
}

subms[subs]++;
if(ms[subs]<subms[subs])
{
flag = false;
break;
}
}
if(flag) ans.emplace_back(i);
}

return ans;
}
};
  • 标题: 字符串
  • 作者: 卡布叻_米菲
  • 创建于 : 2023-04-11 20:30:00
  • 更新于 : 2024-02-08 13:08:49
  • 链接: https://carolinebaby.github.io/2023/04/11/字符串/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.15.8