字符集 charset 和字符编码 character encoding

参考：https://www.cnblogs.com/skynet/archive/2011/05/03/2035105.html

字符集是个集合，指明了其支持的所有字符有哪些。字符编码则为字符集中的每个字符指定了一个数字代号，解析的时候把代号替换为具体图形展示给用户。

常用的字符集有：

ASCII：包含控制字符，英文，数字等。单字节字符编码，对应的字符编码就是 ASCII 码GB2312Unicode：对应的字符编码有： UTF-8：变长字符编码，可以表示任意 Unicode 编码，兼容 ASCII 编码（是 ASCII 的超集）。UTF-16UTF-32：4字节编码，定长，效率低

字符串是跟字符集绑定在一起的，每个字符串都要按照特定的字符集进行解析，否则就可能看到乱码。

字符串常见操作

通常在每种语言中，用双引号表示字符串，单引号表示字符。

最长公共前缀 LCP（Longest Common Prefix）：表示两个字符串从头开始最长的相同子串。

对字符串及字串求哈希

哈希函数特点：

每个哈希函数的值域是固定的对于不同的输入，其在值域内的分布大致均匀同一个输入，哈希值唯一输入的微小变动也会引起哈希函数值的巨大变化不同输入，其哈希值可能相同，称为碰撞（冲突），但概率较低

字符串的哈希值，通常用 unsigned long long 类型（uint64）。过长时自由溢出即可。

字符串哈希函数

参考：https://oi-wiki.org/string/hash/

每次比较一个字符串的时间复杂度为 O(len(s))，如果把字符串映射为一个整数，就可以把时间复杂度降低为 O(1)。这个映射过程就是哈希，通常采用多项式哈希： $$Hash(s)=\sum _{i=0}^{len(s)-1}s[i]\ast p^i$$ 其中 p 是常数，通常取质数（例如 7，233 等）。在超出表示范围时，上式中的结果会自由溢出。当然也可以对某个特定的数字 M 取模，这样结果都落在 [0, M) 中： $$Hash(s)=\sum _{i=0}^{len(s)-1}s[i]\ast p^i(\mathrm{m}\mathrm{o}\mathrm{d}M)$$ 如果 b 和 M 互质，在输入随机的情况下，这个 Hash 函数在 [0, M) 上每个值概率相等，此时单次比较的错误率为 $\frac{1}{M}$。所以，哈希的模数一般会选用大质数。

例如（C 语言 math 库中的 pow 函数中有变量时，gcc 编译时需要加 -lm 参数）：

// c language int hash(char *str) { int i = 0; int h = 0; int p = 7; while(str[i] != '\0') { h += str[i] * ((int)pow(p, i)); i++; } return h; }

golang 示例：

package main import ( "fmt" "math" ) func hash(str string) uint64 { h := 0.0 p := 7 for i, v := range str { h += float64(v) * math.Pow(float64(p), float64(i)) } return uint64(h) } func main() { fmt.Println(hash("")) fmt.Println(hash("a")) fmt.Println(hash("b")) fmt.Println(hash("abcdflsjgoiutewfdxs")) fmt.Println(hash("abcdflsjgoiutewfdxsa")) fmt.Println(hash("abcdflsjgoiutewfdxss")) fmt.Println(hash("abcdflsjgoiutewfdxsfwajojovjdsojslkg")) }

输出：

0 97 98 219083135877256352 1324775968858451456 1529956082195168000 9223372036854775808

后缀哈希函数

$$Has{h}_s(i)=\{\begin{array}{r}0,i=len(s)\\ Has{h}_s(i+1)\ast p+s[i],0<=i<len(s)\end{array}$$

子串哈希函数

用 Hash_s(i, L) 表示字串 s[i, i + L - 1] 的哈希值，则： $$Has{h}_s(i,L)=Has{h}_s(i)-Has{h}_s(i+L)\ast p^L$$

字典树 TRIE

字典树应用场景：给定一个字符串集合S，给定Q个询问，每个询问给定一个串 t，判断 t 是否是集合S中某个字符串的前缀。

如果用暴力，时间复杂度为：O(Q * len(t) * len(S))。如果用字典树，需要加上构造树的时间，总时间复杂度为：O(Q * len(t) + ${\sum }_{s\in S}len(s)$。

字典树 C 代码

这里假设字符串最多只包含 3 个字符，只能是 26 个小写字母。从根节点开始，每个节点有 26 个分支，最多有 1 + 26 + 26 * 26 + 26 * 26 * 26 个节点。

字典树-数组实现

创建一个二维数组，每行放 26 个元素，总行数跟字符串最大长度相关。初始化的时候，从 0 行的特定字符开始，如果数组中这个元素为0，则计数值加一并赋值，非0，则直接跳转到这一行。这样，字典树中每个字符都指向一行数据，且每行数据最多仅有一个字符指过来。

#include <stdio.h> #include <string.h> #define MAXN 1 + 26 + 26 * 26 + 26 * 26 * 26 #define MAXCHAR 26 int trie[MAXN][MAXCHAR]; int tot; void trie_insert(char *s) { int root = 0; int len = strlen(s); for (int i = 0; i < len; i++) { if (trie[root][s[i] - 'a'] == 0) { trie[root][s[i] - 'a'] = ++tot; } root = trie[root][s[i] - 'a']; } } int trie_search(char *prefix) { int root = 0; int len = strlen(prefix); for (int i = 0; i < len; i++) { if (trie[root][prefix[i] - 'a'] == 0) { return 0; } root = trie[root][prefix[i] - 'a']; } return 1; } int main(void) { trie_insert("abc"); trie_insert("aaa"); // for (int i = 0; i < MAXN; i++) { // for (int j = 0; j < MAXCHAR; j++) { // printf("%d ", trie[i][j]); // } // printf("\n"); // } printf("%d--1\n", trie_search("")); printf("%d--1\n", trie_search("a")); printf("%d--0\n", trie_search("b")); printf("%d--1\n", trie_search("ab")); printf("%d--0\n", trie_search("ba")); printf("%d--1\n", trie_search("aa")); printf("%d--1\n", trie_search("abc")); printf("%d--0\n", trie_search("aba")); // 全量插入长度为 3 2 1 0 的字符串来验证代码 /* trie_insert(""); char s2[2]; s2[1] = '\0'; for (int i = 0; i < 26; i++) { s2[0] = 'a' + i; trie_insert(s2); } char s3[3]; s3[2] = '\0'; for (int i = 0; i < 26; i++) { for (int j = 0; j < 26; j++) { s3[0] = 'a' + i; s3[1] = 'a' + j; trie_insert(s3); } } char s[4]; s[3] = '\0'; for (int i = 0; i < 26; i++) { for (int j = 0; j < 26; j++) { for (int k = 0; k < 26; k++) { s[0] = 'a' + i; s[1] = 'a' + j; s[2] = 'a' + k; trie_insert(s); } } } */ // for (int i = 0; i < MAXN; i++) { // for (int j = 0; j < MAXCHAR; j++) { // printf("%d ", trie[i][j]); // } // printf("\n"); // } return 0; }

字典树-链表

#include <stdio.h> #include <malloc.h> #include <string.h> #define MAXCHAR 26 typedef struct trie_node { char value; struct trie_node* next[MAXCHAR]; } trie_node; typedef struct trie { trie_node* root; } trie; trie trie_init() { trie_node* tmp = (trie_node*)malloc(sizeof(trie_node)); trie t = {tmp}; return t; } void trie_insert(trie t, char *s) { int len = strlen(s); trie_node* cur = t.root; for (int i = 0; i < len; i++) { int id = s[i] - 'a'; if (cur->next[id] == NULL) { trie_node* tmp = (trie_node*)malloc(sizeof(trie_node)); tmp->value = s[i]; cur->next[id] = tmp; } cur = cur->next[id]; } } int trie_search(trie t, char *s) { int len = strlen(s); trie_node* cur = t.root; for (int i = 0; i < len; i++) { int id = s[i] - 'a'; if (cur->next[id] == NULL) { return 0; } cur = cur->next[id]; } return 1; } int main(void) { trie t = trie_init(); trie_insert(t, "abc"); trie_insert(t, "aaa"); printf("%d--1\n", trie_search(t, "a")); printf("%d--1\n", trie_search(t, "aa")); printf("%d--1\n", trie_search(t, "abc")); printf("%d--0\n", trie_search(t, "ac")); printf("%d--0\n", trie_search(t, "b")); return 0; }

例子

用字符串哈希执行字符串匹配

给定模式串 t，给定 Q 组询问，每组询问给定一个待匹配串 s。对每组询问分别回答待匹配串 s 是否包含 t 作为字串。

暴力

对每个字符串 s， 从首个字符开始跟 t 逐个对比，直到碰到不相同的字符或某个字符串结束为止。

时间复杂度：O(Q * len(t) * len(s))

字符串哈希

对模式串 t 求哈希，对每个字符串 s 的长为 len(t) 的子串求哈希，并逐个与 t 的哈希对比。

时间复杂度：O(Q * len(s) + len(t))

判断相似字符串

字符串等长且只有一位不同，就称为相似。给定 N 个长度均为 L 且都不相同的字符串，每个串只包含大小写字母和数字，求有多少对相似。N<=30000，L<=200。

暴力

对于每个字符串，逐个跟后面的所有字符串每位进行对比。

时间复杂度：O(N ^ 2 * L)

字符串哈希

对于每个字符串，枚举删除某一位后的子串并计算哈希。然后判断这些子串哈希出现的次数。 时间复杂度：O(N * L * L + N * L)

判断字符串是不是前缀

给定字符串集合S，给定字符串t，判断t是集合中哪些字符串的前缀。

#include <stdio.h> #include <string.h> #define MAXN 1 + 26 + 26 * 26 + 26 * 26 * 26 #define MAXCHAR 26 int trie[MAXN][MAXCHAR]; int tot; void trie_insert(char *s) { int root = 0; int len = strlen(s); for (int i = 0; i < len; i++) { if (trie[root][s[i] - 'a'] == 0) { trie[root][s[i] - 'a'] = ++tot; } root = trie[root][s[i] - 'a']; } } int trie_search(char *prefix) { int root = 0; int len = strlen(prefix); for (int i = 0; i < len; i++) { if (trie[root][prefix[i] - 'a'] == 0) { return 0; } root = trie[root][prefix[i] - 'a']; } return 1; } int main(void) { trie_insert("abc"); trie_insert("aaa"); printf("%d--1\n", trie_search("aa")); printf("%d--0\n", trie_search("ad")); return 0; }

求给定整数集合中，最大的异或值

给定整数集合 $S=\{a_0,a_1,...,a_n\}$，对任意两个元素做异或运算 XOR，求最大值。