如何找到最長的alphebetical子字符串C++

我想寫一個函數，當給定一個字符串時，它將返回按字母順序排序的最長的子字符串。事實證明，這非常困難，儘管我嘗試過很多次，但是距離開始的時間並不近。如何找到最長的alphebetical子字符串C++

的功能應該做的一個例子：

abacdefkabfhxy應該返回abcdefkxy abacdefkabfhixy應該返回abcdefhixy

感謝您的幫助！

2013-11-15 user906357

這被稱爲最長遞增子問題：http://en.wikipedia.org/wiki/Longest_increasing_subsequence –

可能重複的[查找最長增加序列]（http://stackoverflow.com/questions/4938833/find-longest-increasing-sequence） – Dukeling

另一個 - [如何確定最長的增長子程序使用動態編程？]（http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming） – Dukeling

請嘗試以下操作。它不檢查字符是字母，但你可以很容易地將自己添加該條件：

#include <iostream> 
#include <vector> 
#include <utility> 
#include <algorithm> 
#include <string> 

std::string longest_alpha_substr(const std::string& str) 
{ 
    char last = str[0]; 
    int size = 1; 
    unsigned int i = 1; 
    std::vector<std::pair<int, int>> pairs; 

    for (; i < str.size(); ++i) 
    { 
     if (str[i] >= last) 
     { 
      last = str[i]; 
      ++size; 
     } else 
     { 
      pairs.push_back(std::make_pair(i - size, size)); 
      size = 1; 
      last = str[i]; 
     } 
    } 

    pairs.push_back(std::make_pair(i - size, size)); 

    using pair_type = std::pair<int, int>; 

    auto max = std::max_element(pairs.begin(), pairs.end(), 
           [] (const pair_type& p1, const pair_type& p2) 
    { 
     return p1.second < p2.second; 
    }); 

    return str.substr(max->first, max->second); 
} 

int main() 
{ 
    std::string str = "ghijkdefghijabcde"; 
    std::cout << longest_alpha_substr(str); // "defghij" 
}

來源

2013-11-15 21:46:38 0x499602D2

對於每個字母賦予值A = 1，B = 2 ... Z = 26。

現在求解最長增加子序列問題。

你會得到一個數量遞增的序列。

將它們轉換回字母，就完成了。

A [1..N] - 輸入序列 L [j]的最長=嚴格遞增子序列在位置j結束

遞推公式：

L[j] = max of i such that i<j & A[i] <A[j] {L[i]} + 1

來源

2013-11-16 02:10:53 arunmoezhi

如何找到最長的alphebetical子字符串C++

回答

相關問題