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
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) ?
Pas de solution correcte
Autres conseils
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow