Блог

Главная - Вопросы по программированию - Как мне уменьшить временную сложность этого палиндрома подстроки?

Как мне уменьшить временную сложность этого палиндрома подстроки?

#c #time-complexity #palindrome #substr

#c #временная сложность #палиндром #substr

Вопрос:

Я решаю эту проблему, ввод: строка, вывод: самая длинная подстрока, которая является палиндромом, я решил ее следующим образом в O (n ^ 3). Я пытаюсь решить это в O (n ^ 2). Пожалуйста, помогите. Вот код:

 int isPalindrome(string str){
    for(int i = 0, j = str.size()-1 ; i < j ;i  ,j--){
        if(str[i] != str[j])
            return 1; //1 is the minimal palindrome length
    }
    return str.size();// return length of palindrome
}

string longestPalindromicSubstring(string str) {

    int maxLength = 0;
    string result = "";
    
    for(int i = 0; i < str.size(); i  ){ 
            for(int j = 1; j <= str.size(); j  ){ 
                string temp = str.substr(i,j); //substring of length j

                if(temp.size() > maxLength){
                  int count = isPalindrome(temp);
                    if(count>maxLength){
                        maxLength = count;
                        result = temp; //saving the substring as result
                    }
                }
            }// j for loop ends
    } //i loop ends
    
  return resu<
}

Комментарии:

1.Еще один. Ссылка.Просто найдите «самую длинную палиндромную подстроку», вы получите много таких статей. Если вам нужен O(n) подход, тогда используйте алгоритм Манахера. Реализация.В этой статье есть 4 набора, ссылка на следующий находится в конце.

2. Другие статьи об алгоритме Манахера: 1 , 2 , 3 . Если вам нужна O(n^2) временная сложность, вы также можете взглянуть на решение с использованием DP. Ref. Но это решение DP имеет O(n^2) пространственную сложность, в то время как те, которые я упомянул в приведенном выше комментарии, имеют сложность O(1) .

Ответ №1:

 pair<int,int> getPalindromeRange(string str, int left, int right){
    while(left>=0 amp;amp; right<str.length()){
        if(str[left] != str[right]) 
            break;
        left--;
        right  ;
    }
    return make_pair(left 1, right);
}


string longestPalindromicSubstring(string str) {

    pair<int,int>longestRange{0,1};//first value is starting index and second value is the length of the substring
    
    string result ="";

    for(int i=1 ;i<str.length(); i  ){
        pair<int,int>odd = getPalindromeRange(str, i-1, i 1);
        pair<int,int>even = getPalindromeRange(str, i-1, i);
        
        if(longestRange.second - longestRange.first < odd.second - odd.first)
            longestRange = odd;
        
        if(longestRange.second - longestRange.first < even.second - even.first)
            longestRange = even;

        if (longestRange.second - longestRange.first == str.length())
            break;
        
    }//for loop ends
    result = str.substr(longestRange.first, longestRange.second -longestRange.first);
    
  return resu<
}