僅使用基本字串操作計算字串中子字串的最大連續出現次數

int longest_str(std::string str, std::string dna) {
    int longest_count = 0;
    int current_count = 0;
    std::string temp;
    for (int i = 0; i <= (dna.size() - str.size());   i) {
      if (dna.at(i) == str.at(0)) {
          
        for (int j = i; j < i   str.size();   j) {
          temp.push_back(dna.at(j));
        }
        if (temp.compare(str) == 0) {
          current_count  ;
          temp.clear();
          i  = str.size();

      
        } else if (temp.compare(str) != 0) {
          if (current_count >= longest_count) {
            longest_count = current_count;
          }
          temp.clear();
          current_count = 0;
  
        } 
      } else if (dna.at(i) != str.at(0)) {
        if (current_count >= longest_count) {
          longest_count = current_count;
        }
        continue;
      }
        
  }
    
  return longest_count;
}

基本上我在這里要做的是遍歷給定的 DNA 鏈，當我遇到 STR 的第一個字母時，比如在索引 i 處，我將附加來自 DNA 的下一個 i str.size() 字母鏈到一個臨時變數。然后，我將該臨時變數與 STR 進行比較，如果相等，則將當前計數加 1，清除臨時字串，相應地增加索引，然后重復該程序。如果臨時字串不等于 STR，我將清除字串，更新最長計數到該點，并將當前計數重置為 0。如果遇到不等于 STR 的第一個字符的字符，我將同樣更新最長計數，將當前計數重置為 0，然后重復該程序。

例如，如果給定的 DNA 是“GTATTAATTAATTAATTAGTA”，而 STR 是“ATTA”，這個函式應該回傳 4。

當我針對不同的輸入進行測驗時，該函式一直給我看似任意的答案，所以我不確定這里出了什么問題。我的猜測是我更新最長計數變數的方式有問題。有什么建議么？

uj5u.com熱心網友回復：

問題是你這樣做：

i  = str.size()

但是你忘記了你的回圈本身也在增加 i，所以你實際上是在跳過一個索引。

第二個問題是您可能會在之前退出回圈

      if (current_count >= longest_count) {
        longest_count = current_count;
      }

如果您的最后一個匹配小于字串的長度（或者如果您的最后一個匹配正好在字串的末尾結束），則執行。

這是您的代碼的骯臟修復：

int longest_str(std::string str, std::string dna) {
    int longest_count = 0;
    int current_count = 0;
    std::string temp;
    for (int i = 0; i <= (dna.size() - str.size());   i) {

      if (dna.at(i) == str.at(0)) {
          
        for (int j = i; j < i   str.size();   j) {
          temp.push_back(dna.at(j));
        }
        
        if (temp.compare(str) == 0) {
          current_count  ;
          temp.clear();
          i  = (str.size()-1);
        } else if (temp.compare(str) != 0) {
          temp.clear();
          current_count = 0;
        }
        if (current_count >= longest_count) {
          longest_count = current_count;
        }
      } else if (dna.at(i) != str.at(0)) {
        if (current_count >= longest_count) {
          longest_count = current_count;
        }
        continue;
      }
        
  }
    
  return longest_count;
}

其他解決方案可能更清潔，但希望您現在能看到問題。

您可能錯過的另一個問題是當您的字串包含重疊匹配時會發生什么。例如：

“阿塔塔塔”

使用您的代碼，您將找到第一個“ATTA”，但您不會找到重疊的“ATTAATTA”，因此您實際上需要重新考慮您的邏輯

uj5u.com熱心網友回復：

我為您的代碼撰寫了一個更簡潔的實作：

#include <iostream>

size_t longestStr(std::string dna, std::string str)
{
    size_t temp_ans = 0, final_ans;

    for (size_t i = 0; i < dna.size(); i  )
    {
        if (dna[i] == str[0])
        {
            final_ans = 0;
            while (dna.substr(i, str.size()) == str)
            {
                if (  final_ans > ans)
                {
                    ans  ;
                }
                i  = str.size();
            }
            i -= (str.size() * final_ans);
        }
    }

    return ans;
}

int main()
{
    std::cout << longestStr("GTATTAATTAATTAATTAGTAATTAATTAATTAATTAATTAATTAGTA", "ATTA");
}

輸出：

6

不需要temp。
此外，您最好使用size_t而不是int因為max size of a string > int.

標籤：C 细绳

上一篇：如何使用CMake和-L/usr/include/mariadb/mysql-lmariadbclient編譯C

下一篇：-ffast-math的奇怪LTO行為