c++ - 我的 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) 时间。所以这应该是 O(nm) 其中 n 和 m 是字符串的长度。是否超过 O(nm) ？

Answer 1

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