字符串操作与质数查找算法详解

今天我们将深入探讨两个C++编程题目，分别是"A-Substrings"和"B-Calling Extraterrestrial Intelligence Again"。这两道题目分别涉及到字符串处理和算法设计，展示了不同的编程技巧。 首先，让我们看"A-Substrings"题目。该题目的核心是找到一个给定字符串数组中最短的子串，这个子串在所有其他字符串中都不出现。通过读入字符串长度n和n个字符串p[i]，程序遍历每个字符串，计算长度，并记录最小长度（mi）以及对应的索引f。然后，创建两个临时字符串str1和str2，用于存储可能的子串。接着，对于已找到的最小长度子串p[f]，逐字符构建str1和str2，检查这两个子串是否在其他字符串p[k]中出现。如果未发现匹配，则更新最长无重复子串的长度（ma）。最后，输出最长无重复子串的长度。 第二个题目"B-Calling Extraterrestrial Intelligence Again"更偏向于算法与数据结构的应用。题目要求寻找一定范围内（1到10000）的所有质数，并用一个布尔数组visit表示哪些数字已被标记为非质数。这里使用了埃拉托斯特尼筛法（Sieve of Eratosthenes）来高效地获取质数。函数getprime()初始化visit数组并将所有小于或等于10000的数字标记为未访问。然后，对每个未访问的数i，如果它是质数，则将其添加到prime数组中，并标记其倍数为已访问。同时，当i能被某个质数整除时，退出内层循环，以避免重复标记。最后，数组prime中存储的就是1到10000范围内的质数。 总结来说，这两个题目分别考察了字符串处理中的模式匹配和数据结构中的质数筛选，展示了C++语言在这些特定场景下的运用。通过解决这些问题，你将提升对字符串操作、查找算法以及数论知识的理解。在实际编程中，熟练掌握这些技巧对于提高代码效率和解决问题能力是非常有帮助的。