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
문제
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) ?
올바른 솔루션이 없습니다
다른 팁
제휴하지 않습니다 StackOverflow