优雅解决字符串移位包含问题：C++标准库函数实战指南

在编程竞赛和日常开发中，字符串处理是绕不开的基础技能。面对"判断一个字符串是否可以通过循环移位包含另一个字符串"这类经典问题时，许多开发者会本能地写出多层嵌套的暴力枚举代码。这种解法虽然直观，但往往效率低下且容易出错。实际上，C++标准库已经为我们准备了强大的工具—— strstr 和 find 函数，能够以更优雅的方式解决这类问题。

1. 理解字符串移位包含问题

字符串移位包含问题要求判断一个字符串（称为主串）经过若干次循环移位后，是否能够包含另一个字符串（称为模式串）作为其子串。例如：

• 主串"ABCD"，模式串"CDAB"：将"ABCD"循环左移两位得到"CDAB"，包含模式串
• 主串"ABCD"，模式串"ACBD"：无论如何移位都无法包含

解决这个问题的关键在于两点：

1. 如何高效生成所有可能的循环移位结果
2. 如何快速判断子串关系

传统暴力解法通常需要O(n²)的时间复杂度，而利用标准库函数可以将复杂度优化到接近O(n)。

2. C风格字符串的strstr解决方案

对于使用字符数组(C风格字符串)的场景， <cstring> 头文件中的 strstr 函数是理想的工具。它的原型如下：

char* strstr(const char* haystack, const char* needle);

这个函数在 haystack 中查找 needle 第一次出现的位置，如果找到则返回指向该位置的指针，否则返回 NULL 。

2.1 使用strstr的完整实现

#include <cstring>
#include <iostream>
using namespace std;

bool isCyclicInclude(char s1[], char s2[]) {
    int len1 = strlen(s1), len2 = strlen(s2);
    if (len1 < len2) return false;  // 主串必须更长
    
    char doubled[len1 * 2 + 1];     // 构造s1+s1的字符串
    strcpy(doubled, s1);
    strcat(doubled, s1);
    
    return strstr(doubled, s2) != nullptr;
}

int main() {
    char s1[100], s2[100];
    cin >> s1 >> s2;
    cout << (isCyclicInclude(s1, s2) ? "true" : "false");
    return 0;
}

关键技巧 ：将主串复制一份连接到自身后面，这样所有可能的循环移位结果都会出现在这个新字符串中。例如：

• 原串"ABCD" → "ABCDABCD"
• 左移0位："ABCD"
• 左移1位："BCDA"
• 左移2位："CDAB"
• 左移3位："DABC"

2.2 性能分析

这种方法的时间复杂度主要取决于：

1. 构造双倍字符串：O(n)
2. strstr函数查找：平均O(n+m)，最坏O(n×m)

虽然理论最坏情况与暴力法相同，但实际中strstr经过高度优化，通常表现更好。

3. C++ string类的find解决方案

对于使用C++ string 类的情况，成员函数 find 提供了更现代、更安全的替代方案。其基本用法：

size_t find(const string& str, size_t pos = 0) const;

当找不到子串时，返回 string::npos （一个特殊常量）。

3.1 使用find的完整实现

#include <iostream>
#include <string>
using namespace std;

bool isCyclicInclude(const string& s1, const string& s2) {
    if (s1.length() < s2.length()) return false;
    string doubled = s1 + s1;
    return doubled.find(s2) != string::npos;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    cout << (isCyclicInclude(s1, s2) ? "true" : "false");
    return 0;
}

3.2 string类的优势

相比C风格字符串， string 类的解决方案有几个明显优势：

1. 内存管理自动化 ：无需手动分配/释放内存
2. 长度信息内置 ：不需要strlen调用
3. 接口更丰富 ：除了find，还有rfind、find_first_of等
4. 安全性更高 ：减少了缓冲区溢出的风险

4. 竞赛中的实战技巧

在编程竞赛如NOI、OpenJudge等场景中，字符串处理问题十分常见。以下是几个提高解题效率的建议：

4.1 输入输出优化

对于大规模数据，C风格字符串的输入输出通常更快：

char s1[100000], s2[100000];
scanf("%s %s", s1, s2);  // 比cin更快

4.2 避免不必要的拷贝

对于特别长的字符串，构造双倍字符串可能消耗较多内存。可以改为：

bool isCyclicInclude(const string& s1, const string& s2) {
    if (s1.length() != s2.length()) return false;
    return (s1 + s1).find(s2) != string::npos;
}

4.3 边界条件处理

实际编码时要特别注意以下边界情况：

• 两个字符串长度不等
• 空字符串
• 完全相同的情况
• 模式串是主串的真子串

5. 进阶思考：KMP算法的应用

虽然strstr和find已经足够解决大多数问题，但在极端性能要求的场景下，可以考虑专门的字串匹配算法。KMP算法能在O(n)时间内完成匹配：

// KMP算法实现
bool kmpSearch(const string& text, const string& pattern) {
    // 构建部分匹配表
    vector<int> lps(pattern.length(), 0);
    for (int i = 1, len = 0; i < pattern.length(); ) {
        if (pattern[i] == pattern[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    
    // 执行搜索
    for (int i = 0, j = 0; i < text.length(); ) {
        if (text[i] == pattern[j]) { i++; j++; }
        if (j == pattern.length()) return true;
        else if (i < text.length() && text[i] != pattern[j]) {
            j ? j = lps[j - 1] : i++;
        }
    }
    return false;
}

将KMP与双倍字符串技巧结合，可以得到理论上最优的解决方案。不过在实际编程竞赛中，标准库函数通常已经足够。