C++代码时间复杂度求解及是否为暴力算法问询

代码功能概述 #

这段代码逻辑是：给定初始字符串s和目标子串x，每次将s自身拼接翻倍，检查x是否成为s的子串，最多尝试size2次，返回首次匹配时的拼接次数，失败则返回-1。

时间复杂度分析 #

这段代码的时间复杂度为 O(size1 * size2 * 2^size2)，推导如下：

• 每次循环中，字符串s的长度会翻倍：第count次循环时，s的长度为size1 * 2^count
• C++标准库的string::find最坏情况采用朴素子串匹配逻辑，时间复杂度为O(L*M)（L为母串长度，M为子串长度），因此每次匹配的时间为O(size1*2^count * size2)
• 循环最多执行size2次，总运算量为各次循环的时间之和：size1*size2*(2^size2 - 1)，忽略常数项后即为指数级的O(size1 * size2 * 2^size2)

输入规模较大时超时的原因 #

超时核心在于指数级的时间复杂度和内存消耗：

• 时间层面：当size2增大时，2^size2会呈爆炸式增长，比如size2=20时2^20≈1e6，size2=30时2^30≈1e9，运算量直接超出程序时间限制
• 内存层面：每次s += s会让字符串长度翻倍，当size2较大时，s的长度会达到size1*2^size2，很快耗尽内存，进一步拖慢程序运行

是否属于暴力算法 #

是的，这属于典型的暴力算法：

• 它通过暴力枚举拼接次数的方式，尝试所有可能的拼接情况（最多size2次）
• 子串匹配采用朴素的逐个比对逻辑（最坏情况），未使用KMP、Boyer-Moore等高效子串匹配算法
• 整体思路无优化，完全依赖 brute-force 的枚举和匹配解决问题

原代码 #

#include <iostream>
#include <string>

using namespace std;

int string_addition(int t) {
    std::string s, x, temp;
    int size1, size2;
    
    cin >> size1 >> size2;
    cin >> s;
    cin >> x;
        
    temp = s;
    int checkval = -1;

    for (int count = 0; count < size2; count++) { 
        bool isFound = s.find(x) != string::npos;
        if (isFound) {
            checkval = count;
                 
            break;
        }

        s += s;  
    }
         
    return checkval;            
}

int main() {
    int test_cases;
    cin >> test_cases;
    for (int i = 0; i < test_cases; i++) {
        int result = string_addition(test_cases);
        cout << result << endl;
    }
    return 0;
} 

内容的提问来源于stack exchange，提问作者ArnavK