加速C++尋找最長的迴文

Question

我正在練習Koeing加速C++，並想驗證我的答案。由於網上沒有可用的解決方案，我想在這裏發佈，並請專家查看我的解決方案。我不確定人們是否會喜歡我在這裏發佈。如果沒有，請讓我知道，我將來不會這樣做。此外，它不是作業，它完全是我希望將我的C++技能提升到更高水平的願望。

問題：編寫一個程序來查找字典中的所有迴文。接下來，找到最長的迴文。

我到目前爲止所做的工作 - >我定義了測試迴文的函數，也將所有單詞存儲在一個列表中。我已經在下面發佈了我的代碼。

我卡在哪裏：我需要建議，無論我選擇使用列表數據結構而不是使用列表數據結構嗎？其次，我堅持如何顯示最長的單詞。我可以顯示最長的字，但不是最長的字。

我嘗試下面

bool palindromeTest(const std::string& input) 
{ 
    typedef std::string::size_type strSize; 
    strSize i = 0; 
    strSize j = input.size() - 1 ; 
    while(i < input.size()) 
    { 
     if (input[i] != input[j]) 
     { 
      return false; 
     } 
     i++; 
     j--; 
    } 

    return true; 
} 



int main() 
{ 

    // stores all words in a list or vector 
    std::list< string> listDict; 
    std::string readWord; 
    std::ifstream readFile("/Users/apple/palidndrome-ch5-10/dict.txt"); 
    if(! readFile) 
    { 
     std::cout <<" failed to open file" << std::endl; 
     return 0; 
    } 
    while(readFile >> readWord) 
    { 
     listDict.push_back(readWord); 
    } 

    std::string::size_type maxLen = 0 ; 
    std::string longestWord = " "; // to store longest palindrome 


    // print all the palindrome words and also which is longest palindrome. 

    for(std::list<std::string>::const_iterator it = listDict.begin(); it != listDict.end(); ++it) 
    { 

     if(palindromeTest(*it) ) 
     { 
      std::cout <<" the word -> " << *it << " is palindrome" << std::endl; 
      // find max len of palindrome; 
      maxLen = max(maxLen, it->size()); 
      longestWord = *it ;// need to change code here ?? no idea how 

     } 

    } 

    std::cout <<" the maximum len is = " << maxLen << std::endl; 
    std::cout << " the word with maximum length is " << longestWord ; // something is wrong here 


    return 0; 
} 

Answer 1

載體，並列出兩個同樣出色的工作在這裏，雖然載體是更有效的。

你可以通過改變

maxLen = max(maxLen, it->size()); 
      longestWord = *it ;// need to change code here ?? no idea how 

到

if (it->size() >= longestWord.size()) {longestWord = *it;} 

找到最長的單詞（你實際上並不需要跟蹤的MAXLEN因爲你可以調用longestWord.size（）。 ）

Answer 2

首先進行迴文測試。您正在檢查字符串中每個不需要的字符兩次。在這種特殊情況下，它並不重要，因爲它只是使特定操作的時間加倍，對於某些類似的操作，它會改變語義（考慮reverse - 概念上與迴文測試非常相似）。爲了改進檢查，您可以使用從0到input.size()/2的循環計數器，或使用兩個指針/迭代器並運行，直到它們在中間相遇。還要注意迭代到input.size()/2會留下一個字符，它從來沒有測試過奇數大小的字符串，但這很好。

當需要順序容器時，應始終默認爲std::vector<>，而不是std::list<>。要手動查找最大值，應該將該調用更改爲max，以進行檢查該元素是否大於先前的最大值，然後更新max值和字符串位置（或字符串本身）的測試。在這種特殊情況下，如果重複次數很多，您也可以考慮不使用順序容器，而是使用關聯容器（std::set<std::string>）以避免重複。但最好不要將這些單詞存儲在內存中。

你應該學會使用迭代器，以及標準庫中的迭代器標題。例如，讀取循環可轉化爲：

std::vector<std::string> words; 
std::copy(std::istream_iterator<std::string>(readFile), 
      std::istream_iterator<std::string>(), 
      std::back_inserter(words); 

的迴文的檢查可以對std::equal算法打電話：

bool isPalindrome(std::string const & str) { 
    return std::equal(str.begin(), str.begin()+str.size()/2, 
         str.rbegin()); 
} 

尋找最長迴文也可以用一種算法完成通過提供適當的算符：

的std ::矢量::爲const_iterator最大= 的std :: max_element（words.begin（），words.end（）， []（的std :: string常量& lhs，std :: string const & rhs）{ return lhs.size（）< rhs.size（）; }）;

（使用C++ 11 lambda表達式，在C++ 03你需要創建一個執行同樣的比較，這需要一些更多的樣板代碼函子，但不應該是複雜得多）

正如Antimony指出的那樣，如果你只需要這個結果，你就不需要把所有的單詞都保存在內存中，這樣你就可以按照讀過的來測試每個單詞，只有當它是最長的迴文時才存儲它，現在。這對於標準算法來說不是那麼容易實現的，而且只是推出自己的循環會更簡單。

雖然學習的目的，你可能想跟着書（即針對C++ 03），在C++ 11一個簡單的解決方案可能是：

std::string longestPalindrome(std::istream& stream) { 
    std::string longest; 
    std::for_each(std::istream_iterator<std::string>(stream), 
        std::istream_iterator<std::string>(), 
        [&longest](std::string const & word) { 
         // if is longest palindrome so far 
         if (std::equal(word.begin(), 
             word.begin()+word.size()/2, 
             word.rbegin() 
          && word.size() > longest.size())) 
         { 
         longest = word; 
         } 
        }); 
    return longest; 
} 
int main() { 
    std::ifstream readFile("/Users/apple/palidndrome-ch5-10/dict.txt"); 
    if (!readFile) { 
     std::cerr << "failed to open file\n";  // [*] 
     exit(1); 
    } 
    std::string longest = longestPalindrome(readFile); 
    std::cout << "The longest palindrome is: '" << longest << "'\n"; 
} 

[*]：請注意，除非你真的需要它，最好只輸出「\ n」而不是std::endl。兩者的區別在於std::endl也將刷新流（強制寫入），這會影響性能，沒有特別的原因。至於當你需要沖洗，基本上當你需要確保輸出端產生現在，例如向用戶詢問時：

std::cout << "Enter a number: " << std::flush; // Ensure that the user gets the message 
               // before we lock waiting for an answer: 
std::cin >> number; 

即使在這種情況下，它是更清晰（如果你需要一個換行符）轉儲「\ n」和std::flush比std::endl（其中它不是很清楚，沖洗是故意的，因爲有太多的代碼，使用std::endl無止境地...