Runtime computation of my implementation of LCS

Question

Please help me in trying to find the runtime of my implementation of largest common substring problem

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;
}

the function std::find takes O(n) time right. So this should be O(nm) where n and m are lengths of the strings. IS it more than O(nm) ?

Answer 1

Worst Case of Your Implementation is the case where the two strings are identical. In this case Time Complexity is O(n*m) ,n-> outer loop ,m ->find or extending the match BTW you dont have to use temp string ,just use counter of the length