字符串处理基础知识(II) ++++++++++++++++++++++++++++++++ **子串** :strong:`子串`\ （substring），又叫\ :strong:`子字符串`\ ，是字符串处理技术中特别重要的一个基本概念。子串是指一个字符串中的任意一个连续片段，子串单独拿出来也是一个字符串。例如 ``"abc"`` 是 ``"abcdef"`` 的子串，它由后者的前3个连续字符构成。又如 ``"world"`` 是字符串 ``"hello world"`` 的子串。对于子串在原串中的位置范围，一律采用含头不含尾的原则用左闭右开区间表示。 特殊地，一个字符串中的任何一个单独的字符都构成这个字符串的子串。例如 ``"a", "b", "c"`` 都是字符串 ``"abc"`` 的子串。 更特殊的，空字符串 ``""`` 是任何一个字符串的子串，字符串本身也是它自己的一个子串。所以空字符串 ``""`` 也有而且只有一个子串，就是空字符串 ``""`` 本身。 请注意，子串和上一节的子序列问题中所说的子序列是不同的。子串必须是连续的一个片段，而子序列可以不连续，只要保持字符的顺序不变即可。 长度为 :math:`n` 的字符串，它的子串一共有 :math:`\frac{n(n+1)}{2}+1` 个，是 :math:`O(n^2)` 的量级。它的子序列个数是 :math:`2^n` 个，比子串个数的量级要高得多。 子串的最基本操作有两个：提取和搜索。 :strong:`子串提取`\ ，也叫\ :strong:`字符串切片`\ ，是指从一个字符串中切出指定范围的片段，获得一个子串的操作。 :strong:`子串搜索`\ ，也叫\ :strong:`子串匹配`\ ，是指在一个字符串中搜索是否存在与另一个字符串相同的子串的操作。 **C-string的子串处理** ``cstring`` 库中提供了一些库函数用于C-string的子串操作，功能虽不是特别强，但能满足大多数基本需要。 由于C-string本是个数组，子串提取相当方便。\ ``cstring`` 库提供了两个库函数 ``strcpy()`` 和 ``strncpy()`` 用于复制C-string内容。前者用于完整地复制一个C-string的内容到另一个C-string中去；后者则可以额外指定复制的最大字符数，如果源字符串有那么多个字符就复制那么多个字符，如果没有就复制到源字符串末尾为止。这两个函数的用法如下： .. code-block:: c++ char s1[20] = "hello world"; char s2[20] = { 0 }, s3[20] = { 0 }, s4[20] = { 0 }; strcpy(s2, s1); // 完整地复制s1到s2中去，s2成为 "hello world" strcpy(s3, s1+6); // 复制从s1[6]开始到s1末尾的所有内容复制给s3，即 "world" strncpy(s4, s1+7, 2); // 从s1[7]开始复制2个字符给s4，即 "or" .. warning:: 1. 使用 ``strcpy()`` 和 ``strncpy()`` 时一定要注意，需要编程人员自己来确保目标位置的字符数组空间足够，函数不会检查会否超限。 2. 函数参数的顺序是目标字符串在前，源字符串在后，这一点很容易搞错。 3. ``strncpy()`` 函数在复制完指定数量的字符后并不会自动在目标末尾添加空字符 ``'\0'``\ ，这也是编程人员的责任。 实际上，自己写一个根据起始位置和长度提取子串的工具函数也很简单，请务必尝试一下。 ``cstring`` 库当然也提供了用于子串搜索的库函数，\ ``strstr()`` 和 ``strcasestr()``\ ，后者和前者唯一的区别是搜索时忽略大小写，所以我们仅对 ``strstr()`` 的用法进行简单的介绍。 .. hint:: 事实上，子串搜索是一个非常重要的算法类型，包括许多经典的搜索和匹配算法，比如经典的KMP算法、比较复杂的通配符匹配、非常强大但也非常复杂的正则表达式等。以后我们会专题学习这些算法。但在实际编程时如果仅是需要用到子串搜索的功能，那么使用库函数是更好的选择。 如果去看 ``strstr()`` 函数的说明，可以发现它接受两个参数，前一个叫 ``const char *haystack``\ ，意思是“干草堆”，后一个叫 ``const char *needle``\ ，意思是“针”，函数的原型如下： .. code-block:: c++ char *strstr(const char *haystack, const char *needle); 看来英语里并没有“大海捞针”这个成语，但一定有“干草堆里找针”这种说法，而早期C语言标准库的设计者们显然认为子串搜索就是一件类似“干草堆里找针”的麻烦事情。这个函数的功能就是从干草堆字符串 ``haystack`` 中去搜索第一个和针字符串 ``needle`` 内容一致的子串，返回的是子串的起始位置指针。如果找不到这根针，那么返回的是空指针 ``NULL``\ 。特殊地，如果针是空字符串，那么返回的就是干草堆的指针。 例如： .. code-block:: c++ char s1[20] = "hello world", s2[20] = "or"; char *p1 = strstr(s1, s2); // 将返回指向s1中第一次出现 "or" 的首位置，即 s1+7 char *p2 = strstr(s1, "World"); // 将返回空指针NULL，表示搜索不到 "World" char *p3 = strcasestr(s1, "World"); // 忽略大小写后，将返回s1+6 .. admonition:: 练习 请思考一下，假如在干草堆中不止有一根针，如何利用 ``strstr()`` 函数把所有这些针的位置都依次找出来？ 例如，从 ``"this is the Mississippi"`` 中搜索 ``"is"``\ ，一共会有4个，请编写一个程序把它们从前往后一个个地都找出来，并依次输出每一个子串 ``"is"`` 的起始位置。 相比之下，C++ string的子串处理功能就强大多了，使用起来也更加方便。但是现在先不做介绍，留待以后遇到时再说。接下来先学习两个字符串处理的基础题：最长无重复字符子串和Z字形变换。这两个题目来自著名的力扣（LeetCode）网站，它们在处理技巧上比上一节的两题略有提升。 .. index:: 【最长无重复字符子串】, 〖LeetCode#3〗 最长无重复字符子串（LeetCode#3） ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 问题：输入一个长度不超过80的字符串 ``s``\ ，找出其中最长的不含重复字符的子串的长度。 例如： 输入 ``"abcabcbb"``\ ，应输出3，因为其中最长的无重复字符子串为 ``"abc"`` 或 ``bca`` 或 ``cab``\ ，长度均为3，没有比这更长的了。 输入 ``"aaaaaaaa"``\ ，应输出1。 输入 ``"pwwkew"``\ ，则应输出3，对应的子串为 ``"wke"`` 或 ``"kew"``\ 。 假如暴力枚举输入字符串中的所有子串，并逐个检查子串中是否有重复字符，那么这个算法的时间复杂度会很高。我们前面说过，一个长度为 :math:`n` 的字符串，其子串数量为 :math:`O(n^2)` 级。判断一个字符串中是否有重复字符，需要从头到尾遍历每一个字符，所以这种暴力枚举法的时间复杂度为 :math:`O(n^3)` 级别，显然太慢了。 事实上，我们可以通过记录每一个字符在字符串中上一次出现的位置，实现一遍扫描解决问题，时间复杂度为 :math:`O(n)`\ 。 我们用一个整数数组 ``int p[128]`` 来存放每一个字符在 ``s`` 中上一次出现的位置，例如 ``p['a']`` 表示字符 ``'a'`` 在 ``s`` 中上一次出现的位置。用两个位置索引 ``i`` 和 ``j`` 分别表示无重复字符子串头尾两端的位置，初始值全部为0。然后我们让 ``j`` 从头到尾地扫描 ``s`` 中的每一个字符 ``s[j]``\ 。每扫描一个字符就做如下操作： 1、如果 ``p[s[j]] >= i``\ ，也就是说字符 ``s[j]`` 上一次在 ``s`` 中出现的位置不在子串头位置 ``i`` 之前，说明在子串 ``s[i:j]`` 内已经有和 ``s[j]`` 重复的字符出现过了，位置就在 ``p[s[j]]`` 。例如下面这种情况： .. code-block:: none s: abcdefghcbd ^ ^ i=0 j=8 此时'c'字符上一次出现的位置为：p['c'] = 2，而 i = 0 这种情况下，今后的无重复字符子串的头部就应该从该字符上一次出现的位置之后开始了，所以我们把 ``i`` 调整为 ``p[s[j]] + 1``\ ，然后把 ``p[s[j]]`` 改为 ``j``\ ： .. code-block:: none s: abcdefghcbd ^ ^ i=3 j=8 调整后，i 变为 p['c'] + 1 = 3，而表示'c'字符上一次出现位置的 p['c'] 则改为了 j = 8 这样，子串 ``s[i:j]`` 就能始终保持无重复字符，并且随着 ``j`` 的逐渐后移一直跟踪着 ``s`` 中的所有无重复字符子串。 2、如果 ``p[s[j]] < i``\ ，说明字符 ``s[j]`` 没有在 ``s`` 中出现过或者仅在子串 ``s[i:j]`` 之前出现过，总之不在当前考虑的范围之内。例如上面这个例子中，当 ``j`` 继续向后移动一个字符时： .. code-block:: none s: abcdefghcbd ^ ^ i=3 j=9 字符'b'曾经出现过，位置为 p['b'] = 1，但是当前 i = 3 > 1 这说明上次那个'b'现在已经不用考虑了，相当于从来没有出现过 所以这种情况下只要简单地更新一下 ``s[j]`` 的出现位置，让 ``p[s[j]] = j`` 即可。 3、上述步骤处理完之后，\ ``i`` 和 ``j`` 就指向了一个新的无重复字符子串，长度为 ``j - i + 1``\ ，而我们的算法就是要统计出每一个这种长度中的最大值，这应该是一个很熟悉的操作了吧。 下面就是实现上述算法过程的程序代码： .. literalinclude:: ../../codes/232_lc3.cpp :language: c++ .. note:: 由于ASCII字符编码的最大值为127，所以位置数组 ``pos`` 的长度为128。 使用了块操作一次性给 ``pos`` 数组的所有元素设置初始值-1，如果忘了块操作和 ``memset()`` 函数的用法，请复习这里：:ref:`批量赋值`\ 。 .. admonition:: 练习 这个题目还有另一种 :math:`O(n)` 时间的算法，它不记录每一个字符上一次出现的位置，而是记录它出现的次数。当某个字符第一次出现重复的时候，根据一定的规则去调整 ``i`` 和 ``j`` 的值。这个算法在思路上和我们用的算法是一致的，都是滑动窗口的思路，只是在实现方式上略有改变。请设计出这种算法并编程验证。 .. index:: 【Z字形变换】, 〖LeetCode#6〗 Z字形变换（LeetCode#6） ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 问题：将一个字符串根据指定的行数，以从上往下、从左到右的顺序进行Z字形排列。比如输入字符串 ``"CPLUSPLUSISGREAT"``\ ，行数为3时，排列如下： .. code-block:: none C S S R P U P U I G E T L L S A 按照这样的方式排列后，再按照从左往右逐行读取的方式产生出一个新的字符串 ``"CSSRPUPUIGETLLSA"``\ ，将这个经过了Z字形变换得到的新字符串输出。 如果将上述字符串做4行的Z形排列，则为： .. code-block:: none C L R P P U G E L S S S A U I T 于是应该输出的变形后的字符串为 ``"CLRPPUGELSSSAUIT"``\ 。 指定的行数大于0。特殊地，如果指定行数为1或大于字符串长度，那么变形后的字符串和原串是相同的。 **解题思路** 这个问题咋看上去比较混乱，其实并不难。因为字符串，无论是C-string还是C++ string，其实都是一个字符型数据的顺序列表，都可以通过指定位置来访问其中的每一个字符。而这个题目要做的无非是按照一套特定的规则去遍历访问一个字符串中的所有字符而已。所以我们只要分析出Z字形变换之后的新字符串中每一个字符与它在原字符串里位置的对应关系，就可以实现这个变换了。 仍以字符串 ``"CPLUSPLUSISGREAT"`` 为例，它的长度为16个字符，位置编号从0到15。现在排成3行的Z字形，可以列出每个位置上的字符在原串中的位置编号如下： .. code-block:: none 0 4 8 12 1 3 5 7 9 11 13 15 2 6 10 14 如果排成4行的Z字形： .. code-block:: none 0 6 12 1 5 7 11 13 2 4 8 10 14 3 9 15 设行数为R，按照Z字形排列的规则，第0行和第R-1行这两行是没有斜排字符的。 如果我们把竖排字符的列叫做“主列”，那么我们可以发现，每一行上各个主列上字符的位置编号构成了一个等差数列，首项就是行号。因为一共有R行，而且相邻两个主列之间一共有R-2个斜排字符，所以公差都是2R-2。这样我们就可以很方便地按照规则输出所有的主列字符了。 但是，在第1到第R-2行中，相邻主列之间还有斜排字符，因此在每次输出一个主列元素之后，先要输出它后面的那个斜排字符（假如有的话）。观察排列后的位置编号很容易发现，每一行上的斜排字符位置编号同样形成一个公差为2R-2的等差数列，而且它的首项加行号一定等于2R-2。这是因为每一行的第2个主列字符位置为行号加2R-2，从它回退到第一个斜排字符，恰好经历一上一下长度为两倍行号的一段折线，因此就有第一个斜排字符的位置等于行号加2R-2再减2个行号，即2R-2-行号。 这样我们就可以很方便地用一个从0到R-1的循环来完成整个变换了。在每一轮循环中输出该行的字符，首先计算出该行主列字符和斜排字符的位置首项，然后在不超出原字符串长度的范围内逐项进行输出即可。 .. tip:: ``cstdio`` 库中有多个函数可以进行单字符输入输出，一般都建议使用 ``getchar()`` 和 ``putchar()`` 这一对函数，它们是所有输入输出函数中运行速度最快的。使用方法也非常简单，如果要输入一个字符到变量 ``c`` 中去，就用 ``c = getchar();`` 语句；如果是要输出一个字符 ``c``\ ，那么 ``putchar(c)`` 即可，当然也可以直接输出字符字面量，例如：\ ``putchar('\n')``\ 。 另外，单纯地输出一个字符串为一行时也建议使用函数 ``puts()``\ ，例如 ``puts("Hello World!");``\ 。比用 ``printf()`` 要简单很多，而且它会自动加上换行，不需要人为在字符串后面加 ``'\n'``\ 。 下面是代码： .. literalinclude:: ../../codes/232_lc6.cpp :language: c++ .. admonition:: 思考 这个算法需要特别注意的地方是对输入的行数一定要有特判，否则当行数为1时算法会出现严重的问题：死循环！请想一想这是为什么？