字符串

字符串，是由零个或多个字符组成的有限序列。一般记为：$S = a_1a_2...a_n$ 。串的长度为 0 时，称为空串。

子串：字符串中任意个连续的字符组成的子序列称为该串的子串。

在主串中的位置：字符或子串在主串中第一次出现的位置，从 1 开始计数。

串的操作

获取子串

bool subString(String &sub, String s, int pos, int len) {
    // 判断子串位置是否合法
    if (pos < 1 || pos > s.length || len < 0 || len > s.length - pos + 1) return false;
    for (int i = 0; i < len; i += 1) {
        sub.str[i] = s.str[pos + i - 1];
    }
    sub.length = len;
    return true;
}

串的比较

0. 根据码点来确定字符的大小；
1. 从第一个字符开始逐个比较，先出现更大字符的串大；
2. 在 1 的基础上，若一个串的长度小于另一个串，则小；若长度相等，则相等。

int compare(String s1, String s2) {
    for (int i = 0; i < s1.length && i < s2.length; i += 1) {
        if (s1.str[i] != s2.str[i]) return s1.str[i] - s2.str[i];
    }
    return s1.length - s2.length;
}

子串的定位

int index(String s, String t) {
    int i = 1, n = s.length, m = t.length;
    String sub;
    while (i <= n - m + 1) {
        subString(sub, s, i, m);
        if (compare(sub, t) != 0) i += 1;
        else return i;
    }
    return 0;
}

串的存储结构

顺序存储

静态分配：

#define MAXLEN 255
typedef struct {
    char str[MAXLEN]; // 一个字符占 1B
    int length;
} String;

动态分配：

#define MAXLEN 255
typedef struct {
    char *str; // 需手动分配内存，且记得释放
    int length;
} String;

串长度标记方式即优缺点：

• 如上声明，单独用一个 int 存放长度。
• 将数组第一位存放串的长度。优点：位序与数组下标一致；缺点：串长度不能超过 255。
• 用 \0 标记结尾。缺点：不方便获取串的长度。
• 最优：舍弃数组第 0 位，用一个 int 存放串的长度。

串的链式存储

typedef struct StringNode {
    char ch;    // 每个结点只存放一个字符，存储密度低。
    struct StringNode *next;
} StringNode, *String;

或者每个单元存放多个字符：

#define CHUNKSIZE 4
typedef struct StringNode {
    char str[CHUNKSIZE];
    struct Chunk *next;
} StringNode, *String;

模式匹配

• 主串；
• 模式串：要在主串中查找的字符串；
• 子串：主串中与模式串相匹配的子串。

朴素的模式匹配算法

时间复杂度：$O(nm)$

int index(String s, String t) {
    int i = 1, j = 1;
    while (i <= s.length && j <= t.length) {
        if (s.str[i - 1] == t.str[j - 1]) {
            i += 1;
            j += 1;
        } else {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > t.length) return i - t.length;
    else return 0;
}

KMP 算法

时间复杂度：$O(n+m)$

int kmp(String s, String t) {
    int i = 1, j = 1;
    while (i <= s.length && j <= t.length) {
        if (j == 0 || s.str[i - 1] == t.str[j - 1]) {
            i += 1;
            j += 1;
        } else {
            j = next[j];
        }
    }
    if (j > t.length) return i - t.length;
    else return 0;
}

计算 next 数组：

void get_next(String t, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < t.length) {
        if (j == 0 || t.str[i - 1] == t.str[j - 1]) {
            i += 1;
            j += 1;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}