Расчет времени выполнения моей реализации LCS
Пожалуйста, помогите мне найти время выполнения моей самой большой проблемы с подстрокой
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 (нм)?
Решение
Наихудший случай вашей реализации — это случай, когда две строки идентичны. В этом случае временная сложность равна O (n * m), n-> внешний цикл, m -> найти или расширить соответствие.
Кстати, вам не нужно использовать временную строку, просто используйте счетчик длины
Другие решения
Других решений пока нет …