我的LCS实现的运行时计算

Question

请帮我寻找最长公共子串问题实现的运行时间。

int main(){
    string a;
    string b;
    cin>>a>>b;
    string::iterator a1,b1;
    string max,temp;

    for(a1=a.begin();a1!=a.end();a1++){

        b1=find(b.begin(),b.end(),*a1);
        if(b1!=b.end()){
            temp+=(*b1);
            while( ((b1+1) != (b.end())) and ((*(a1+1))==(*(b1+1)))){

                a1++;
                b1++;
                temp+=(*b1);
            }
            if(max.size()<temp.size()){
                max.assign(temp);

            }
            temp.clear();
        }

    }
    cout<<max;
}

函数 std::find 的时间复杂度是 O(n)，这意味着对于两个字符串长度分别为 n 和 m，使用该函数的时间复杂度应为 O(nm)。但是，它是否会比 O(nm) 更高？

- Soumadeep Saha

---

std::sort 的时间复杂度为 O(n log n)（大多数标准排序算法的实现也是如此）。此外，还要记住不能忽略 find 步骤所需的时间，其时间复杂度为 O(m)。基于这些，你认为运行时间是多少？ - templatetypedef

你必须使用动态规划来解决它，时间复杂度为O(n.m)。 - Jarod42

@templatetypedef 我从未使用过 sort。我的意思是 find，因此需要调用 n 次 find，每次调用需要 O(m) 的时间，那么总时间复杂度就是 O(nm)，对吗？ - Soumadeep Saha

用 a = "abbbbbba" 和 b = "ababbbbbba" 进行测试，你的结果是错误的。 - Jarod42

O(nm)是否大于O(nm)? 不，它们相等 :-). 请纠正这段文字。还有比O(nm)更高的复杂度吗？ - Gangnus

Answer 1

你的实现最坏情况是两个字符串完全相同的情况。在这种情况下，时间复杂度为O(n*m)，其中n->外部循环，m->查找或扩展匹配。 顺便说一句，你不需要使用临时字符串，只需使用长度计数器即可。

- Shokrof