《王道程序员求职宝典》笔记 - 第2章 字符串

子串与子序列的一些概念

• 子串：连续字符组成的子序列。
• 子序列：不要求连续，但要求顺序需与主串中一致，例如”abcd”的子序列可以是”ac”也可以是”ab”。
• 空串是所有字符串的子串。
• 字符串是他自身的子串。

标准库函数不对内存进行检查，但VS的Debug模式会 使用字符串标准库时需注意有内存越界的可能，标准库不负责检查字符串边界。VS中存在Debug和Release模式，Debug模式下字符串的库函数会打开assert检查内存，错误程序会出现异常。

字符串查找子串的经典算法

• BF算法：待补充。
• KMP算法：待补充。

判断$s_2$能否被$s_1$包含 直接判断$s_1s_1$是否包含$s_2$即可，因为$s_1s_1$已经包含了$s_1$的所有移位的情况

$s_2$比$s_1$短，如何判断$s_2$中的字母都在$s_1$中存在

• 分别排序后遍历。
• 利用hash表。
• 利用素数原理（如何获得素数表？）。

字符串单词逆序问题 如将”Welcom to Beijing”转换成”Beijing to Welcom”，通常的做法是先将所有字母逆序，再将每个单词逆序。

删除字符串中指定的一些字符 例如删除”hello world”中的aeiou，变为”hll wrld”。

• 遍历。
• 简历哈希表，利用hashmap进行查询。
• 每个字母为一个素数，将第一个字符串中代表的素数相乘得到一个结果，再将这个结果除以第二个字符串中每一个字母所代表的素数，如果能整除证明包含这个字符，如果不能整除代表不包含这个字符。
• 简历hash表遍历。

删除字符串前后的空格，再将中间多的空格合并成一个 先前后删除，之后合并中间。

习题

待补充。